The Kremlin leader flew to Tajikistan for a summit of a regional security forum with China and four Central Asian states at which the crisis in Georgia was likely to be discussed.
Moscow's allies in the former Soviet Union, Asia and elsewhere usually side with the Kremlin against the West on contentious issues, but have been notable for their silence since Russia fought a brief war with Georgia this month.
Citing the need to avert a "genocide" against civilians, Moscow sent troops and tanks into Georgia's breakaway South Ossetia and a second pro-Moscow region, Abkhazia, this month.
On Tuesday the Kremlin recognised them as independent states, prompting Georgia to withdraw all but two of its diplomats from Moscow. The Georgian parliament was to debate the future of ties with its giant northern neighbour on Thursday.
Georgia's close ally, the United States, and European powers have demanded Russia respect a French-brokered ceasefire and withdraw all its troops from Georgia, including a Moscow-imposed buffer zone whose legitimacy is disputed.
The Group of Seven rich nations, in a joint statement on Wednesday, also condemned Russia's recognition of Georgia's rebel regions and what it described as its excessive use of military force in Georgia.
Analysts see Moscow's actions as a bid to halt expanding Western influence in the Caucasus, a major oil and gas transit route from the Caspian Sea to the West that bypasses Russia.
The biggest prize for Russia would be to win the support of China when Medvedev meets President Hu Jintao at the summit of the Shanghai Cooperation Organisation (SCO) in the Tajik capital Dushanbe.
SEPARATIST FEARS
The SCO is dominated by Russia and China and includes Tajikistan, Uzbekistan, Kazakhstan and Uzbekistan. It claims the role of a security guarantor in Central Asia.
Chinese Foreign Ministry spokesman Qin Gang told reporters in Beijing that South Ossetia would probably be discussed. But with most SCO members facing separatist rebellions of their own, outright support for Moscow's actions is seen as unlikely.
"China, which has own separatists, will be the biggest problem," said Alexei Mukhin, head of the Centre of Political Information think-tank. "The recognition of Abkhazia and South Ossetia is unacceptable for Beijing."
The ex-Soviet Central Asian state have built their foreign policy strategies on trying to maintain a balance between loyalty to Moscow and building ties with the West.
Analysts say the most Medvedev can hope for is that SCO leaders will say they understand Russia's motives, without going any further.
Moscow said it did not fear being isolated over recognising Georgia's rebel provinces, saying drumming up support for its position was not its primary goal.
"We're not going to twist anyone's hands to make them support (recognition)," said Dmitry Peskov, spokesman for Russian Prime Minister Vladimir Putin.
WORRIED NEIGHBOURS
Russia's continued military presence in Georgia has angered the West -- European leaders are to discuss their response at an emergency summit on Monday.
Moscow says the troops are needed to protect civilians from Georgian aggression and that their presence is provided for under a French-brokered ceasefire, a view disputed by Paris.
The Georgia crisis has alarmed other former Soviet republics with sizeable Russian minorities, particularly Ukraine and the Baltic states.
Foreign Secretary David Miliband, on a visit to NATO aspirant Ukraine, said Medvedev had a big responsibility not to start a new Cold War.
But in reality, the West has little leverage over a newly confident Russia rolling in cash from high oil and gas prices.
Ukrainian President Viktor Yushchenko, who like Saakashvili has irked Moscow by seeking to join NATO and move out of Moscow's orbit, has condemned Russia's war with Georgia.
Yushchenko told Reuters he wanted to raise the question of increasing Russia's rent on its Sevastopol base in Ukraine's Crimea region, the headquarters of the Russian Black Sea fleet.
Moscow says any renegotiation would break a 1997 deal under which Moscow leases the base for $98 million (53 million pounds) a year until 2017.
Georgia's President Mikheil Saakashvili on Thursday accused Russia of planning to "redraw the map of Europe by force".
"If Moscow can oust Georgia's democratically elected government, it can then intimidate other democratic European governments. Where will this end?" he wrote in the Financial Times.