ICC Prosecutor Luis Moreno-Ocampo asked the court for an arrest warrant for President Omar Hassan al-Bashir, the most senior figure pursued by the court since it was set up in 2002.
Bashir is also the first sitting head of state charged by an international court since Liberia's Charles Taylor and Yugoslavia's Slobodan Milosevic.
Moreno-Ocampo said Sudan's armed forces and the militia they support killed up to 35,000 people while 2.5 million others were subject to a campaign of "rape, hunger and fear" in refugee camps, where he said genocide continued "under our eyes".
"The decision to start the genocide was taken by Bashir personally," he told a news conference. "Bashir is executing this genocide without gas chambers, without bullets, without machetes. It is a genocide by attrition."
Thousands of demonstrators rallied in Khartoum against the ICC on Sunday, while aid organisations and the U.S. embassy have tightened security, fearing an upsurge in violence from an enraged Bashir and emboldened rebels in Darfur.
A few dozen people protested outside the British embassy and the U.N. headquarters in Khartoum after the ICC news.
Khartoum, which is not a party to the court and has denied genocide in Darfur, said it would ignore the announcement. However, it pledged to continue peace efforts and to protect U.N. staff in Darfur, home to the world's largest humanitarian operation.
Sudan will seek support from allies such as China and Russia to get the U.N. Security Council -- which asked the ICC to investigate crimes in Darfur in 2005 -- to block a warrant, but France said Sudan must respect the ICC.
"The coming stage will witness a diplomatic battle with the stage in the U.N. headquarters in New York," a Sudanese Foreign Ministry spokesman said, adding he expected support from China, Russia, South Africa, Indonesia and Arab and African groups.
China declined to comment on the case, which arises at a bad time for Khartoum's biggest arms supplier and a major investor in its oil industry just weeks before the Beijing Olympics.
Arab foreign ministers said they would hold an emergency meeting on Saturday to discuss the case against Bashir, a former army general who came to power in a coup in 1989. The African Union was also holding consultations on the indictment.
The chairman of the pan-African body wants the ICC to suspend any moves to arrest Bashir to help efforts to end internal strife in Sudan, which reaches beyond western Darfur into the east and south and to neighbouring nations.
"If you arrest Bashir, you will create a leadership vacuum in Sudan. The outcome could be equal to that of Iraq. There would be an increase in anarchy," Tanzanian Foreign Affairs Minister Bernard Membe told Reuters, speaking on behalf of President Jakaya Kikwete who chairs the African Union.
Human rights groups welcomed the prosecutor's action.
"Charging President al-Bashir for the hideous crimes in Darfur shows that no one is above the law," said Richard Dicker of New York-based Human Rights Watch.
U.N. Secretary-General Ban Ki-moon said he expected Sudan to ensure the safety of U.N. staff there despite the proceedings against Darfur, noting in a statement that the "United Nations must respect the independence of the judicial process".
Moreno-Ocampo said it usually took two to three months for ICC judges to rule on an application for an arrest warrant, but it could take longer as this case was so complicated. He said he would also ask the court to freeze Bashir's assets.
The prosecutor said Bashir masterminded a plan to destroy the Fur, Masalit and Zaghawa ethnic groups in Darfur who launched a rebellion in 2003 against the Khartoum government, accusing it of marginalising the vast western province.
He charged Bashir with three counts of genocide, five of crimes against humanity, including murder, extermination, forcible transfer, torture and rape, and two of war crimes.
The prosecution said Bashir promoted those who complied with his "genocidal orders", such as Humanitarian Affairs Minister Ahmed Haroun, whom the ICC charged last year over Darfur.
He said thousands of women and girls were raped, with perpetrators expressing genocidal intent by saying the victims would bear Arab babies.
"The decision on this indictment is a victory for humanity," said Suleiman Sandal of the Darfur rebel Justice and Equality Movement. "Now this decision will put Bashir in a corner and will help us now to overtake this regime. A criminal man cannot be a president of a member state of the United Nations."
The ICC was set up as the world's first permanent war crimes court to take over from temporary tribunals such as the Sierra Leone court trying Liberia's Taylor, also in The Hague.
It is so far only investigating conflicts in Africa but has no police force and only four suspects in custody. It has issued warrants for six more, including Sudan's Haroun and militia commander Ali Kushayb, who Khartoum refuses to hand over.
International experts say at least 200,000 people have died in Darfur and 2.5 million have been displaced since 2003. Khartoum says 10,000 people have been killed.