Aziz promised on Thursday to solve "all of the country's problems" in his first speech since he removed the president.
The military council now running the country has pledged to respect treaties and other international commitments binding Mauritania, Africa's newest oil producer.
Leaders of the military coup in Mauritania vowed to hold "free and transparent" presidential elections "in the shortest time possible".
The statement released by the leaders on Thursday said: "These elections, which will be held in the shortest possible period, will be free and transparent and will bring for the future a continued and harmonious functioning of all the constitutional powers."
But international reaction to the coup has brought condemnation.
November 1960 - Independence won from France as the Islamic Republic of Mauritania with Moktar Ould Daddah as president.
1964 - Daddah proclaims a one-party state and the next year all parties merge to form the Parti du Peuple Mauritanien.
1975 - Mauritania is declared an Islamic Socialist Republic.
July 1978 - Daddah is deposed in a bloodless coup by Moustapha Ould Mohamed Salek who assumes absolute power as president in March 1979.
December 1984 - After a number of coup attempts, Maaouya Ould Sid'Ahmed Taya seizes power and proclaims himself president. Almost two years later, Taya introduces the Sharia.
January 1992 - Taya is elected president with 63 per cent of the vote under a 1991 constitution permitting multiple political parties.
August 2005 - The army seizes power to end Taya's rule, and promises to hold presidential elections in March 2007.
June 2006 - In a referendum meant to end decades of coup attempts, voters back constitutional changes ensuring no president can serve for more than a decade.
March 2007 - Former minister Sidi Mohamed Ould Cheikh Abdallahi wins a presidential run-off with 53 per cent of the vote defeating opposition figure Ahmed Ould Daddah. Abdallahi was sworn in on April 19.
July 2008 - Abdallahi asks Yahya Ahmed El Waghef, the prime minister to form a cabinet after the PM and his government resign following criticism over the government's response to rising food prices.
August 6, 2008 - Presidential guardsmen seize Abdallahi in a coup after he sacked several senior army officers.
August 7 - An 11-strong military government promises it will work with politicians and civic groups to organise presidential elections.
Todd Moss, the US state department's African affairs representative, told Al Jazeera that the international community has "condemned in the strongest possible terms the unconstitutional overthrowal of the legitimate democratic government".
"The interational community is united in that this is an unacceptable step and unfortunate event for Mauritania and Africa. We hoped to have gotten passed the cycle of coups like this.
"What [Aziz] should have done is organise himself and put himself into the next election cycle - that's what should happen in a democracy," Moss said.
"The entire relationsip [between the US and Mauritania] now needs to be reviewed. If they want the relationship to continue, the president needs to be restored as per the constitution."
The European Commission said on Thursday that Mauritania's democratically-elected president and prime minister must be released by the new junta as a precondition for any fresh elections.
John Clancy, the Commission's spokesman, told reporters in Brussels: "The current situation is unacceptable. A military coup of this nature is unacceptable against a democratically elected president.
"We have taken note of what they said. These elections would have to fit in the framework of the constitution of that country.
"In this connection, the release of the democratically-elected president and prime minister is an essential precondition," he said.
Romain Nadal, the French foreign ministry spokesm, said on Thursday: "Any lack of a return to constitutional legality will necessarily have consequences on relations between Mauritania its main partners, such as the European Union."
Ban Ki-moon, the UN secretary-general, said he "deeply regrets the overthrow of the government of President Sidi Ould Cheikh Abdallahi," and called for "the restoration of constitutional order", his spokeswoman said.
The African Union called for maintaining "constitutional legality" and said Ramtane Lamamra, its peace and security commissioner, would go to Mauritania.
Convoys rolled through the capital on Wednesday, surrounding the presidential palace, the prime minister's office and the state broadcaster.
Officers seized Abdallahi, along with the country's interior minister and Yahya Ould Ahmed Waghf, the prime minister, in a bloodless coup led by Aziz.
Abdel Aziz is the leader of the presidential guard who was fired by Abdallahi shortly beforehand.
Abdallahi himself won elections last year after a 2005 coup, also instigated by Ould Abdel Aziz, which ended years of military rule.