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 national unity government.
The Sudanese president also issued another decree which relieved all states' governors, ministers and mayors as well as state advisors.
Meanwhile, 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.
A new presidential council was sworn-in on Saturday. Al-Bashir was re-sworn-in as the country's president, while Garang, head of the ex-rebel Sudan People's Liberation Movement (SPLM), was sworn- in as the first-vice president and Ali Othman Mohammed Taha as vice president.
According to the new interim constitution signed and approved by the presidential council before the sworn-in ceremony, an interim government of national unity will take office in August.
Garang, ex-southern rebel leader of the Sudan People's Liberation Movement (SPLM), arrived here Friday afternoon for the first time after two decades of civil war.
The Sudanese government under President al-Bashir and Garang's SPLM signed a peace deal on Jan. 9 in the Kenyan capital Nairobi, putting a final seal on the longest civil war in Africa.