Some 200 Ethiopian troops have been seen leaving the Somali capital, four weeks after they crossed the border to help the government defeat Islamists.
Ethiopia's involvement is unpopular in Somalia
"Starting today we will withdraw our forces from Mogadishu," Ethiopia General Suem Hagoss said at a ceremony where warlords surrendered their arms.
Ethiopian Prime Minister Meles Zenawi has told the BBC the withdrawal would take place in three stages.
The African Union is trying to set up a peacekeeping force to replace Ethiopia.
But so far, only Uganda and Malawi have publicly said they would send troops to Somalia.
The BBC's Mohammed Olad in Mogadishu says 200 Ethiopian troops were seen moving out of the airport with armoured vehicles.
Nine battalions proposed - up to 9,000 troops:
Uganda: 1,500 troops offered, subject to parliamentary approval
Malawi: Up to 1,000 troops offered
South Africa: Considering but forces stretched
General Hagoss said they were reducing the number of forces in the country, but was not specific on how many soldiers will be moving out before AU peacekeepers are deployed.
"The heroic army of Ethiopia supported the transitional government to restore normality to the country after 16 years of violence," Somali deputy Prime Minister Hussein Mohamed Aidid told the AFP news agency.
"I thank the people and the government of Ethiopia on behalf of my government."
However, Prime Minister Mohammed Ali Ghedi denied that the Ethiopians had started to leave Somalia, saying they would stay until the African force had arrived.
Ethiopia's intervention to help the government oust Islamists who had taken control of Mogadishu and much of southern Somalia was unpopular with many Somalis.
The two countries have fought several border wars in the past.
A crowd of some 200 people gathered at the former National University to see off the Ethiopians, reports the AP news agency.
"Leave us alone and let us solve our problems," they chanted.
Several of the warlords who have battled for control of Somalia since 1991 have now disbanded their militias.
They have handed their "battle-wagons" - vehicles with mounted anti-aircraft guns - to the government, while the gunmen are to join the putative national army.
But with an estimated 3,500 Islamist fighters in Mogadishu, analysts question whether the government can maintain order without the Ethiopian troops.
Mr Ghedi called for Islamist leader Sheikh Sharif Sheikh Ahmed to be handed over to the Somali government.
He surrendered to the Kenyan authorities at the weekend and is under police guard in a top Nairobi hotel.
He is the most senior Union of Islamic Courts (UIC) official whose whereabouts are known after they were ousted.
Mr Ghedi also said Mr Ahmed could play a role in Somalia's government, which both the US and the UN have called for.
"We have appealed to them to come back home and take part in this [reconciliation] process and Sheikh Sharrif Ahmed is one of them," he said.
US ambassador to Kenya, Michael Ranneberger, who also covers Somalia is to speak to Mr Ahmed this week, possibly on Tuesday, embassy spokesperson Jennifer Barnes told AFP.
"The ambassador will urge [him] to counsel his supporters not to carry out violence and to support the development of an inclusive government," she said.
Meanwhile, at a meeting in Brussels, European Union foreign ministers said they were ready to offer financial support to the proposed peacekeeping force.
The ministers said a sustainable solution to the crisis could be reached, but that there were concerns about the reconciliation of the disparate Somali factions.