Organizers said as many as a million people took part in the rally, the strongest show of defiance by the Khartoum regime so far against Thursday's Security Council resolution demanding prosecution before the Hague-based court of 51 suspects identified by a UN commission of inquiry in January.
Protestors directed much of their anger against British Prime Minister Tony Blair, and French and US presidents Jacques Chirac and George W. Bush, but they also had harsh words for UN chief Kofi Annan.
"Death to Bush, death to Blair, death to Chirac," chanted the demonstrators, many of whom travelled in from the provinces for the rally and arrived hours ahead of the start.
State television had given extensive advance publicity to the march and carried live footage on the day.
Traffic came to a standstill in the capital, as the protestors marched from the republican palace to UN headquarters, calling for Annan to resign.
"No surrender of Sudanese to the International Criminal Court", read one banner carried by the protestors. "We are ready to defend our country," said another.
A 10-strong delegation of demonstrators was allowed to hand in a protest letter at the French embassy, but a heavy security force presence blocked access to the British and US missions.
Police fired tear gas to disperse protestors who attempted to break through their lines.
The Sudanese government has vowed to defy the Security Council's demand for international prosecution of the 51 officials, security force and militia commanders accused of gross violations in the war-wracked western region of Darfur.
President Omar al-Beshir Monday solemnly swore "thrice in the name of Almighty Allah that I shall never hand any Sudanese national to a foreign court."
The defiance prompted warnings from the regime's opponents that it risked sparking outside military intervention.
"If it does not comply by surrendering the suspects to the ICC, (it) will open the door to punishments that will go beyond sanctions to the use of military force," said Abdel Qadir Bakash of the Beja Congress, an ethnic minority rebel group active in eastern Sudan.
He said the regime had two options -- "either to destroy itself and the Sudan as well by refusing to cooperate with the international community, or to agree to participate in a national conference of all opposition political forces ... to establish a broad-based government that will implement the Naivasha peace accords."
Bakash was referring to a landmark peace agreement signed by the government with southern rebels of the Sudan People's Liberation Movement in January ending two decades of civil war.
The UN inquiry in January found that Sudanese government forces and militias had committed abuses including murder, torture, rape and pillage in the suppression of the two-year-old ethnic minority uprising in Darfur.
The scorched earth campaign waged by the government against the rebels has left more than 300,000 dead and 2.4 million people displaced, according to a report by a British parliamentary committee