The final convoy carrying about 150 troops and equipment, which had been based in Batumi in far southwestern Georgia, crossed into Armenia - just after midnight Moscow time (2000 GMT Wednesday), said Russia's Ground Forces spokesman Col. Igor Konashenkov.
"We would better deploy in the territory of a nation which has a positive attitude to us," Konashenkov said in remarks carried by Vesti 24 television.
Despite the withdrawal, about 2,500 Russian peacekeeping forces remain in the separatist-controlled region of Abkhazia, and several hundred more are stationed in another rebel province, South Ossetia, according to official statements.
President Mikhail Saakashvili's government has accused the Russian peacekeepers of backing separatists and pushed for their replacement with a U.N. force. Russia says its peacekeepers were deployed as part of peace agreements in the early 1990s that ended wars between the rebels and the government in Tbilisi.
On Wednesday, Saakashvili claimed that Russia had sent additional forces to Abkhazia to strengthen its support for separatists.
"They deployed several dozen armored vehicles and artillery pieces in Abkhazia and deployed another 200 paratroopers who aren't part of the peacekeeping contingent," he said Wednesday.
Chief of the Russian military's General Staff, Gen. Yuri Baluyevsky, denied the allegations, the ITAR-Tass news agency reported.
Russia had stationed several thousand regular troops at former Soviet bases in Georgia since the 1991 collapse of the USSR. Moscow had pledged to withdraw those troops by the end of 2008, but accelerated the withdrawal as tensions have increased between the two former Soviet nations. The 150 withdrawn troops were the last of them.
Saakashvili this month accused Moscow of fomenting unrest and attempting to overthrow his government by encouraging opposition protests in Tbilisi, the capital.
Russian officials angrily rejected the accusations, and accused Georgia of harassing its soldiers.
"Our servicemen were repeatedly detained by Georgian military police, and our officers couldn't leave their bases," Konashenkov said.
Moscow and Tbilisi continue to argue over the status of the former Soviet base in the Abkhazian town of Gudauta. Russia has said it has withdrawn from the base, but Georgian officials say otherwise.
Kote Gabashvili, the head of the international affairs committee of the Georgian parliament, said Thursday that the Gudauta base still hosts about 800 Russian soldiers and has an airstrip capable of handling large transport planes capable of delivering troops and weapons.
"The so-called peacekeepers have lost their status and effectively deal with splitting Abkhazia from Georgia," Gabashvili told The Associated Press.
Saakashvili's efforts to break with Moscow, integrate into the West and join NATO has put him on a collision course with a newly confident Russia.
Last fall, the Kremlin responded to Georgia's detention of Russian military officers on spying charges with a massive transport blockade and expulsion of Georgians living in Russia.
In August, Georgia claimed that a Russian warplane violated Georgian airspace and released a missile after flying over South Ossetia. The missile, whatever its source, did not explode and no injuries were reported, but the incident raised concerns that Russia was trying to intimidate Georgia.
Russia hotly denied that that one of its warplanes had strayed into Georgia. Some Russian officials accused Georgia of staging the incident to justify sending troops into South Ossetia.
After the 1991 breakup of the USSR, Russian troops remained in the Georgian cities of Batumi and Akhakalakai, and at a base in Tbilisi. Russia still bases troops in Armenia. It also established an air base in ex-Soviet Kyrgyzstan, after the United States opened a base there in 2001 to support military operations in Afghanistan.