Russian Foreign Minister Sergey Lavrov said after meeting with President Saakashvili that the sides have agreed "to take concrete steps" to improve bilateral relations.
In Tbilisi Lavrov led the Russian delegation which attended Saakashvili's presidential inauguration on January 20.
"It is worth of saying that I am holding my first official meeting [after being sworn in as the president] with you," Saakashvili told Lavrov before the meeting. "The meeting, which we are holding now, is significant, because you have probably heard today that [during the inauguration speech] I stressed for several times the importance of relations with Russia. We really believe in it and we really think that we should try once again to start improving our relations, because it has no alternative for us."
In his inauguration speech earlier on January 20 Saakashvili said: "We will continue our movement with even firmer steps towards NATO. This aspiration is not against of any of our neighbor's interests or do not aim at alienating any of our neighbor. We should reach out our hand of cooperation to Russia. We should be friends, we should get closer."
Saakashvili also told the Russian Foreign Minister that during his re-election campaign he had deliberately avoided speaking about "disagreements" persisting in the Russo-Georgian relations.
"We were very cautious towards this issue because we think that now it is not time for throwing stones [at each other], but it is now time to collect them. We have been throwing enough stones during past years. Now, time has come to collect them jointly and try to ensure that our future generations are grateful because all the problems in our relations were settled by us," Saakashvili said. "Therefore, we are always ready and glad to see you here and I think that we really have a chance to build absolutely new relations. We are very glad that you have arrived."
"I appreciate that despite you tight schedule, you found time to meet me. I congratulate you on the re-election and deliver a message of [congratulation] from President Vladimir Putin," Sergey Lavrov responded. "We deemed it absolutely necessary to attend this ceremony at a governmental level. The Georgian people are linked to us with its history - the history, which was friendly, indeed. And we really care how our relations will develop. We have noticed that in your pre-election speeches, in the speeches of your opponents, the issue of Russia was heard in the context of a need to normalize relations."
After the meeting the Russian Foreign Minister told journalists that there are problems in bilateral relations and "these problems are known, so I will not speak about details now."
"I will only say that the Russian side considers necessary to move from the statements about readiness for their [relations'] normalization to concrete steps. Today, during my talks with Mikheil Saakashvili, we heard that the Georgian side has the same attitude. We have agreed to try to take such concrete stems in the near future. I think that it is real," Lavrov said.
Georgian Prime Minister, Lado Gurgenidze said, as he put it, "there is certain cautious optimism" that ties between the two countries would improve.
Before departure from Tbilisi, the Russian Foreign Minister has also met with the opposition leaders.