During the visit, which coincided with the 15th anniversary of the genocide, Mr Blair paid his respects to the victims of the 1994 Rwandan genocide by laying a wreath at the Nyamata genocide memorial outside Kigali.
Speaking at Nyamata, Mr Blair expressed his deepest sympathy to the people of Rwanda and praised them for their determination and compassion which he said is behind the impressive transformation of the country in the last 15 years.
Tony Blair said: "Rwanda has in a remarkably short period of time become a role model for Africa and an inspiration to the world. It is one of the most stable countries in Africa.
"Last year the economy grew by over 10%. A country that was once a no-go area attracted more than a million visitors in 2008. It has pledged to end its dependency on foreign aid. It has become a leading player in the East African Community promoting regional economic integration. Rwandan soldiers are helping to keep the peace in Darfur.
"Rwanda has still a long way to go, and it has an ambitious vision which the Rwandans will have to work hard to achieve - but the country is heading in the right direction thanks to the formidable leadership of President Paul Kagame and the hard work of its people."
Over the weekend, Mr Blair also held a number of meetings with His Excellency Paul Kagame, government leaders and public servants from across Government who are working in partnership with his team of experts to build capacity, strengthen good governance and attract inward investment to Rwanda.
Commenting on the meeting, President Kagame stated: "significant progress has been achieved by Tony Blair's team since their arrival almost a year ago. I can already see evidence of real change, both in my own office as well as across government. The strategy pursued is effective in that Tony Blair's team works with Rwandan counterparts to affect genuine skills transfer. This is a proven method of capacity development that others should emulate."
Tony Blair has had a team of nine experts working in Rwanda since July 2008 to work with President Kagame and his government to build capacity, improve government systems and attract investment, in order to help the President achieve his ambitious vision of economic development and poverty reduction.
Tony Blair staff are providing essential support in key institutions chosen for their strategic importance to that agenda, including the Presidency, the Prime Minister's Office and the Rwanda Development Board, as well as in the country's first think tank, the Institute of Policy Analysis and Research.
The team works shoulder-to-shoulder with Rwandan staff by practically developing the capacity among the next generation of public service leaders to further drive Rwandan development.
The work described here was carried out by the Tony Blair Africa Governance Initiative, it is now being continued by the Tony Blair Institute for Global Change.