Reports suggest some of the generals orchestrated the mass resignation, our correspondent James Copnall says.
Nouakchott airport has been closed, security sources told the AFP news agency on Wednesday.
A journalist based in Nouakchott, Hamdi Ould Mohamed el-Hacen, told the BBC people had gathered on street corners to discuss the coup - in particular the fate of the president and prime minister.
Culture Minister Abdellahi Salem Ould El-Mouallah read a statement on TV on behalf of the coup leaders announcing the presidential decree sacking the top army officers had been "annulled legally and practically".
An army statement said the president was no longer in charge
The first indications of a military coup came as state radio and television were taken off the air amid reports of unusual troop movements in Nouakchott.
The president's daughter, Amal Mint Cheikh Abdallahi, said soldiers seized her father at his house at 0920 local time (0920 GMT).
She raised the alarm in a phone call to a French radio station.
"They came here to find him," she told Radio France International. "They arrested him here and took him to the battalion base. It's a textbook coup d'etat."
The African Union condemned the coup, demanded a return to constitutional government and said it was sending an envoy to Nouakchott immediately.
The governments of South Africa and Nigeria - both major players in the African Union - also criticised the military takeover.
The US state department and the European Commission also decried the coup, with the commission warning it would suspend aid to Mauritania.
Mauritania has a long history of coups, with the military involved in nearly every government since its independence from France in 1960.
Presidential elections held in 2007 ended a two-year period of military rule - the product of a military coup in 2005.
The elections were deemed to have been free and fair and appeared to herald a new era of democracy.
Earlier this year, however, the president dismissed the government amid protests over soaring food prices.
The cabinet that replaced it has been dogged by instability, lacking the support of a moderate Islamist party and a major opposition group that were in the former government.
Mauritania is one of the world's poorest nations as well as its newest oil producer.
The desert nation, a former French colony of more than three million people, has been looking to oil revenues to boost its economy.
I have had no trouble walking around the streets of Nouakchott this morning and as I type, cavalcades of cars are driving around the capital sounding their horns in celebration of the coup d'etat. This being the tribal members of the General and those White Maure with little to do. At night it will be an entirely different matter and I expect the local population will remain indoors as the soldiers here in Mauritania are none too professional. I'm a creature of habit and will be taking my coffee at Cafe Tunis as normal. Ibrahim, Nouakchott Mauritania
The Islamic Republic of Mauritania will never be free and democratic until the Black majority are in full control. It is a time bomb which, if not well organised, may pass through what the Sudan has already passed through. Ahmed Kateregga Musaazi, Kampala, Uganda
I'm a Mauritanian. This putsch is such a pity. We are in the third millennium and this kind of things cannot be acceptable. We have better to improve our economy and not to fight each other. Mohamed Oumar, Kagoshima Japan
Things have been quiet on our side of town but shops are closed for the day. In the slums where we live, people are happy for any kind of change and hope for a better life. The cost of living has increased greatly the past 12 months and people are suffering because salaries have not increased and jobs are few and hard to attain. EZ, Nouakchott, Mauritania
In the south of the country everything is calm at the moment. But a big repatriation operation is going on with the UNHCR, and now the returnees are afraid that the new government won't keep the promises that all people who have been deported in 89 can come back. Laila al amine, Kaedi, Mauritania
With the leadership here in Mauritania, we all knew it was going to happen (the coup), it was just a matter of when. Christian, Nouakchott
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.