Al-Bashir made the decision in consultations with newly sworn-in First-Vice President John Garang at the first meeting of the presidential council, which also includes Vice President Ali Othman Mohammed Taha.
According to the decree, the relieved top officials have been assigned to go on running duties of their ex-ministries till the formation of the new government that will take office in September.
For the purpose, the president also issued another decree which relieved all states' governors, ministers and mayors as well as state advisors.
As another measure to spread the atmosphere of peace and national unity, the president also announced to lift the 16-year- old state of emergency in all states except the states of north Darfur, south Darfur, west Darfur, the Red Sea and Kassala in view of security tensions there.
A new presidential council was sworn-in on Saturday. Al-Bashir was re-sworn-in as the country's president, while Garang, ex- southern rebel leader of the Sudan People's Liberation Movement (SPLM), was sworn-in as the first-vice president and Ali Othman Mohammed Taha as vice president from the original post of the first vice president.
The sworn-in ceremony was witnessed by several heads of state and senior representatives of governments, including UN Secretary General Kofi Annan, Secretary General of Arab League Amr Mousa, Norwegian Minister of International Cooperation Hilde Johnson and US Deputy Secretary of State Robert Zoellick.
There had been a civil war in southern Sudan between the government under President al-Bashir and the SPLM led by Garang, which started in 1983 when the SPLM took up arms fighting for self determination in the southern part of the country, reportedly leaving some two million people dead, mostly through war-induced famine and diseases.
Following nearly eight years of hard negotiations under mediations of African leaders, the two sides finally signed a peace deal on Jan. 9 this year, paving the way for the end of the longest civil war in Africa.
Hailing the peaceful efforts and unity at the sworn-in ceremony, both al-Bashir and Garang vowed to overcome the bitterness of the past and work together in the new partnership during the six-years of an interim period to realize the government of national unity.
"It is important to remove our minds' mines before removing the landmines and to replace them by forgiveness, love and social intimacy," al-Bashir stressed.
Garang said he came to Khartoum not only with his wife, but with the youngest of his children "to show that war is over", adding that the SPLM and the National Congress party under President al- Bashir have delivered to the Sudanese nation a just and honorable peace with dignity for all.
Second vice-president Taha, who had been heading the government delegation for talks with Garang, noted that he and Garang had hammered out the peace agreement despite the hurdles because they were aware of the suffering of the Sudanese people.
"When we started the negotiations, the war was at its peak and men on both sides were fighting viciously for what they believed was right," said Taha, stressing that the will and determination of both sides made a leap from war to peace.
Coincidently with the peace process in the South, the Sudanese authorities also pursued reconciliation with opposition groups in the North in order to reinforce its basis of government.
On June 18, the government and the opposition National Democratic Alliance (NDA) signed an agreement in the Egyptian capital of Cairo ending the sixteen-years dispute between them.
A comprehensive agreement on power sharing was inked by the two sides during the talks, although several major issues including how to divide the seats in the new interim government and the integration of NDA militants into the national forces were left unresolved.
Also speaking at the occasion of the sworn-in ceremony, Annan urged that "the first and most essential task of this new government must be to ensure that peace extends to the whole nation, and that national unity, as prescribed in the comprehensive peace agreement, is made attractive to all of Sudan's people."
The Sudanese new government of national unity should also put the conflicts in Darfur and in eastern Sudan as the immediate priority of their new institution, stressed the UN chief.
Rebels in Sudan's western Darfur region took up arms against the government in February 2003, accusing the central government of neglecting the barren area and arming militia to burn, loot and kill local farmers. During the two-year violence, many people have been killed and displaced.
The central government and two Darfur rebel groups ended their fifth round of talks last week with a broad agreement on the troubled north African nation's unity and "justice and equalities for all".
A document released at the end of the talks stressed "an effective devolution of powers" to regional authorities which mediators said would be further discussed in the talks scheduled for next month.
Meanwhile, the Sudanese government repeatedly accuses Eritrea of backing Sudanese rebels, the Free Lions and the Bija Conference, in eastern Sudan to launch attacks against government forces there.
Vowing to make more efforts to end the conflicts in Darfur and eastern regions, President al-Bashir urged all Sudanese political parties to join hand.
He promised the people in Darfur that the new government would exert utmost efforts to exploit the agreement which the government recently signed with the Darfur rebels, known as the declaration of principles, to realize peace and security in the region.