Russia's South Caucasus Command said the train set off from the suburb of Vaziani at 5 a.m., and is heading for Russia through Azerbaijan.
The Vaziani garrison will be pulled out before the end of the year, ahead of the earliest of the withdrawal deadlines for Russian forces in the South Caucasus state, set for 2007. The defense minister decided on an early pullout in mid-October, amid a diplomatic feud between the former Soviet allies.
The Vaziani base had about a hundred items of equipment and 350 metric tons of ammunition before the first consignment was withdrawn a week ago for redeployment to a base in neighboring Armenia.
Two more consignments are slated for removal in December, with one to be sent to Armenia, and the other to Russia. The garrison's 387 service personnel will leave once the equipment pullout has been completed.
Russia and Georgia have been locked in a bitter diplomatic dispute since September, when four Russian army officers were briefly arrested in Tbilisi on suspicion of espionage.
The move outraged Moscow, which cut transportation and postal links with its neighbor in response, deported hundreds of Georgian migrants and shut down Georgian-run businesses for alleged violations of Russian law.
Georgia's Western-leaning leadership, which seeks to join NATO, is uneasy about Russia's continued military presence, and has repeatedly urged Moscow to withdraw from its Soviet-era bases.
Under a bilateral agreement signed in March 2006 and ratified by Russia's parliament in October, the pullout from the Russian bases in the southern city of Akhalkalaki and in Batumi, in western Georgia, is to be completed by October 1, 2007, and October 1, 2008, respectively.