Delegates cheered and chanted after the signing, which put an end to a 16-year-old feud between the opposition grouping and Sudan's military regime.
The last differences between the two negotiating sides were ironed out Saturday morning, hours before the ceremony which was attended by Sudanese President Omar al-Beshir and Egyptian President Hosni Mubarak, who hosted the week-long talks.
Also present was former southern rebel leader John Garang, whose Sudan People's Liberation Movement is an NDA member but signed a separate peace accord with Khartoum in January, ending a bloody 21-year civil war.
The details of the agreement were not immediately available but it will further reshape Sudan's political landscape, five months after the North-South peace agreement signed in Kenya and as negotiations were under way in Nigeria to end the crisis in Darfur.
The NDA was formed by 13 parties who united in 1989 to oppose the regime only weeks after Beshir seized power in a military coup.
Besides the SPLM, the NDA includes Mirghani's Democratic Unionist Party, one of Sudan's oldest political movements which draws support from the powerful Khatmiya brotherhood, as well as the communist party.
The deal is a significant boost to peace hopes in Africa's largest country, a Nairobi-based expert on Sudan told AFP.
"The agreement with the NDA is essential for broadening the support base of the North-South peace agreement and improving the odds of its success," said David Mozersky, an analyst with the International Crisis Group think-tank.
"But it would not be the end of the process in terms of bringing other political parties on board," he added.
Two ethnic minority rebel groups -- the Darfur-based Sudan Liberation Movement and the mainly Beja Eastern Front -- are also members the deal will not be binding on them.
The SLM is engaged in its own stop-start peace negotiations with the government in Nigeria, while the Eastern Front has an official promise of separate talks of its own.
The Umma party, a northern opposition movement with a large support base, dropped out of the NDA several years ago.
The main issues discussed by Khartoum and the NDA in Cairo were the fate of the opposition movement's armed forces and power-sharing quotas set in the January peace deal for the interim period due to start on July 9.
The NDA came to Cairo hoping to have its forces assimilated in the regular army and the share of power it was granted in the January North-South agreement increased significantly.
Saturday's agreement involves the subsequent dissolution of the NDA in its current form and will eventually bring some of its members into the interim executive.
The current parliament dominated by Beshir's National Congress party is due to be dissolved in the coming days, after it ratifies the North-South peace agreement.
While members of the future interim parliament and government will be appointed in accordance with the quotas reviewed in Saturday's agreement, the political process mapped out in January provides for free elections in three years.
Observers noted that by making up with the NDA, Beshir brings some of his most serious rivals back into the fold. It also consolidates a northern Arab alliance able to counter John Garang's attempts to build a broad non-Arab alliance covering most of southern and western Sudan.