Merkel assured Georgian President Mikheil Saakashvili of Germany's support and pressed for the withdrawal of Russian troops from Georgian territory.
In an apparent change in stance, the chancellor also threw her weight behind Georgia's bid to join the NATO.
"Georgia will become a member of NATO if it wants to -- and it does want to," Merkel said before talks with President Mikheil Saakashvili in Tbilisi.
It was one of the strongest statements yet of support for Georgia's NATO membership bid which is fiercely opposed by Russia. The statement signals a change in Germany's position towards Georgian NATO membership. Earlier this year, Germany led European resistance to plans, pushed by the US, to put Georgia on the track to NATO membership.
Later at a joint news conference with Saakashvili, Merkel said that though Georgia was on a clear path to membership in NATO she stood by her decision at a summit in April not to grant Tbilisi a "membership action plan" for joining the alliance.
At the last NATO summit in Bucharest in April, leaders agreed that Georgia and Ukraine should join the North Atlantic Treaty Organization eventually, but neither nation was given candidate status and no timetables were set.
The United States is strongly in favour of Georgia joining NATO, but misgivings from France and Germany prevented Tbilisi being awarded full candidate status in Bucharest.
Medvedev confirms pull-out
In a meeting with Medvedev in the Black Sea resort of Sochi on Friday, Merkel had criticized Russian actions during the week-long war between Russia and Georgia over the breakaway region of South Ossetia. She demanded that Russia withdraw all its troops from Georgia's core territory.
The Georgian government says rebel Abkhaz forces with the support of Russian troops are occupying 13 Georgian villages, effectively pushing the border of Abkhazia westwards into Georgia proper.
Medvedev said Sunday that Russian regular forces would start their pullout from Georgia on Monday, the Kremlin said.
"From tomorrow, Russia will begin withdrawing its military forces that are supporting Russian peacekeepers," Medvedev told French President Nicolas Sarkozy in a telephone conversation, the Kremlin said in a statement.
Speaking at a Sunday press conference in Tbilisi, Merkel said that despite Medvedev's commitment "according to the information I have available to me this (Russian withdrawal) has not yet begun."
Merkel: Georgia's integrity must be respected
Merkel also repeated that Germany's position was that Georgia's territorial integrity was beyond question, and that its borders should be inviolate.
In her meeting with Medvedev, Merkel also stressed that Germany's position was that Georgia's territorial integrity was beyond question and that Saakashvili was a democratically elected president.
Government sources said ahead of her departure that she intended to push for "a complete cessation of hostilities."
"The ceasefire must be verifiable and lasting," they said.
Georgian media hald back from predictions of what effect, if any, Merkel's visit would have on Russian troops currently occupying Georgian territory.
Rustaveli 2 television described Merkel's presence in Georgia as "part of an international effort to support Georgia."
West divided on how to deal with Russia
German Foreign Minister Frank-Walter Steinmeier warned on Sunday against any knee-jerk reaction to the Caucasus conflict in relations with Russia.
"I do not advise ... any knee-jerk reaction such as suspending talks on a partnership and cooperation agreement (with the European Union). That would signify that such an agreement is more important to the EU than to Russia," Steinmeier said in an interview with German weekly Welt am Sonntag.
"Or Russia joining the World Trade Organisation (WTO): our interest in this is as great as Russia itself. Talks in the NATO-Russian Council are essential too. Because we need open lines of communication -- to Tbilisi and to Moscow," Steinmeier told the paper.
Steinmeier's comments were at odds with the views of other EU members as well as the US.
French President Nicolas Sarkozy, whose country holds the rotating EU presidency until the end of the year, warned on Sunday that Russian relations with the EU would be seriously damaged if Moscow failed to fully implement the peace deal it signed with Georgia.
In a statement, Sarkozy told Medvedev of the "serious consequences that a failure to quickly and fully implement the deal would have on relations between Russia and the European Union."
Britain's Foreign Secretary David Miliband said on Wednesday that the EU should reassess its relations with Russia after its "aggressive" actions in Georgia and decide whether "to proceed with the partnership and cooperation agreement."
US Secretary of State Condoleezza Rice said on Sunday that Moscow's international reputation had taken a beating by its military action in Georgia.
"Russia overreached, used disproportionate force against a small neighbour and is now paying the price for that because Russia's reputation as a potential partner in international institutions, diplomatic, political, security, economic, is frankly, in tatters," Rice told NBC's Meet the Press.
German Chancellor Angela Merkel
"Georgia will become a NATO member if it wants to, and it does want to," German Chancellor Angela Merkel said in an apparent change in Germany's position during her Sunday visit to Tbilisi, Georgia.
Merkel's statement of support for Georgia's NATO membership was one of the strongest yet.
Tbilisi's bid to join NATO is fiercely opposed by Moscow. 

During her meeting with Georgian President Mikheil Saakashvili, Merkel stated that Georgia's territorial integrity and its independence have to be respected. After the meeting Merkel said she expected a 'very prompt' withdrawal of Russian forces from Georgia.

In a telephone conversation with French president Nicolas Sarkozy on Sunday, Russian president Dmitry Medvedev declared that Russian troops would start their pullout from Georgia on Monday. Medvedev explained that Russian troops would be withdrawing to a buffer zone and then to the breakaway province of South Ossetia. It remains unclear how long the withdrawal will take. Sarkozy warned Medvedev on Sunday of serious consequences and damage to the Russian relations with the EU, if Russia failed to fully implement the peace plan it signed. Earlier this week, Britain's Foreign Secretary David Miliband stated that the EU should reassess its relations with Russia after its aggressive actions in Georgia.

A Russian lawmaker has compared the situation in Georgia to Iraq and the U.S. presence there. Konstantin Kosachev, chair of the Russian parliament's security committee told reporters when asked about the withdrawal plan: "If I would ask you in response to the same question how fast the American forces can leave Iraq, for example, the answer would be as soon as we have guarantees for peace and security there."

At the same time, according to Georgian sources, the Russian troops were occupying 13 Georgian villages, pushing the border of Abkhazia into Georgia proper. Russia's Defence Ministry spokesman denied the report, saying that "Russian peacekeepers have been given no orders to move to these populated areas,". There have also been reports of Russian helicopters setting fire to Georgian National Park near Borzhomi. The Russian Defence Ministry's spokesman expressed his surprise and declared that Russian troops were ready to provide assistance in extinguishing the fire if Georgia made an official request. "It is understandable to us that the Georgian authorities are ready to blame the Russian side for any natural disasters on the territory of Georgia," he said.

Russian troops are still occupying the key towns of Gori, north of Tbilisi, and Senako in the west of Georgia. Far from pulling out, Russian military units are entrenching themselves in new positions deeper into Georgia, according to Daily Telegraph. They have also blown up a strategic Georgian Kaspi railway bridge on the main line connecting the country to its neighbours, essentially severing the last route for freight and trade after Russian soldiers also took control of the Georgian main east-west highway.