As part of the agreement Sudan agreed for the first time to create "no-fly zones" over Darfur and promised to ban military flights over rebel-controlled territories in the region.
"It is really a historic moment," Sudanese spokesman Ibrahim Mohammed Ibrahim said. "We will do our most to make sure it is implemented on the ground. Only that will bring peace and stability to Darfurians."
The rebel groups and African Union mediators demanded the no-fly zones following widespread accusations of government bombings of villages, but previous government objections to the provision had stalled the talks.
Sudan's concession toward the rebels comes 10 days before a U.N. Security Council meeting that could have resulted in sanctions on Sudan's oil industry due to the lack of progress in the peace talks and a deteriorating security situation in Darfur.
The accord also calls for the disarming Arab militias, known as the Janjaweed, that have terrorized black villages.
The humanitarian accord guarantees aid workers access to the 1.6 million refugees uprooted from their homes since the conflict began in early 2003. More than 70,000 of Darfur's people have died, mostly through disease and hunger, in what the United Nations is calling the world's worst humanitarian crisis and the United States has called genocide.
"This is a great victory for our people," said Ahmed Hussein Adam, a representative of the smaller rebel group, the Justice and Equality Movement. "We hope this will be the first stage toward the improvement of the situation on the ground."
The agreement came in the third week of talks in the Nigerian capital of Abuja, after two earlier rounds of African Union-sponsored talks failed without any agreements signed.
Despite Tuesday's pact, the groups have yet to reach an agreement on a political accord with long-term solutions to the Darfur crisis.
"We still have a long way to go, but the step we have taken this afternoon is a very important step in the right direction," said Nigerian President Olusegun Obasanjo after a signing ceremony Tuesday.
Participants also expressed doubts whether the new accords would be implemented since an April cease-fire has been widely ignored by all sides.
"These documents won't be worth the paper they are written on if they are not scrupulously implemented on the ground," Obasanjo said, Reuters reported.
The Sudanese government had agreed before to disarm the Janjaweed, and it questioned the definition of the term at the Abuja talks this week. The rebels and the U.S. government has accused the government of backing the Janjaweed, but Khartoum calls its members outlaws and denies any connection to the militia group.
"My question is what is going to happen in practice," Mahgoub Hussain of the Sudan Liberation Army, the larger rebel group, told the Associated Press. "Because we've had ... agreements like this in the past."
The Abuja talks are scheduled to resume Tuesday night to address a common declaration of political principles, Obasanjo said.
A 3,000-strong AU peacekeeping force to protect cease-fire monitors is expected to be in place by the end of the month.