Both the leaders were assisted by their aides during the meeting that lasted for more than 90 minutes. Initially, it was described as a courtesy meeting. They were perturbed over the law and order situation in the country with particular reference to Balochistan and the tribal belt.
They expressed anguish over the 'increased social deprivations' of the masses, stemming from wrong policies of the government.
A joint statement was issued at the end of talks that called for early elections under a neutral setup, return of all political leaders to the country and doing away with all the politically motivated cases. They demanded release of Javed Hashmi, Yousuf Raza Gillani and other political prisoners.
The two leaders dubbed the government as unconstitutional and called for its exit, saying giving more time to rulers could result in serious repercussions for the country.
Sources said both the leaders reiterated their commitment to step up struggle for the restoration of true democracy and not to give in to pressures from any quarters. They pledged to restore 1973 Constitutional as it stood before October 12, 1999.
They will meet on May 14 to sign the 'charter of democracy' and an Alliance for the Restoration of Democracy summit will be held on July 2.
Among others, PPP vice-chairman Makhdoom Amin Fahim, Shahbaz Sharif, Zafar Iqbal Jhagra and Ghous Ali Shah were also present, before their one-on-one meeting at the residence of PML leader.
Hours before their much-talked-about rendezvous, Prime Minister Shaukat Aziz and Pakistan Muslim League president Chaudhry Shujaat Hussain had a one-on-one meeting in Islamabad.
They discussed among other matters, latest political situation with a focus on the Benazir-Nawaz meeting.
Talking to newsmen on Sunday, Nawaz Sharif said his party wanted to introduce a new political culture. "The signing of the charter of democracy will envisage uprooting of dictatorship," he remarked.
The PPP and PML leaders met a day after Pakistan Television telecast an interview of President General Pervez Musharraf and his family, during which the President wished to be remembered as the saviour of Pakistan.
Ms Bhutto was to leave for the United States after the meeting.
Meanwhile, party heads of the Alliance for Restoration of Democracy will meet here on April 30 to discuss the future line of action in the backdrop of Bhutto-Nawaz meeting.
REUTERS ADDS: Benazir Bhutto and Mian Muhammad Nawaz Sharif pledged on Monday to return for 2007 general elections to try to oust the government through the ballot box.
"We want to go back. We are very keen to go back and it is our candid and considered view that the elections cannot be held in a fair and free manner unless and until the two main leaders go back to the country and participate in the election campaign," Nawaz Sharif told Reuters television.
In a separate interview, Benazir Bhutto told Reuters television that while Musharraf had put many obstacles in their path to prevent their return, she believed there was a chance.
"I am planning to go back to Pakistan for the elections of 2007 and I will be discussing this with Mr Sharif," she said.
Bhutto and Sharif both said they were committed to fighting terrorism and that Washington's backing of Musharraf was counter-productive to achieving long-term stability in Pakistan.
"The United States should have its friendship not with one individual in the country," said Sharif. "It should make the people of Pakistan its friends, otherwise this present (US) policy ... is serving nothing else but alienating the 150 million people of the country," he said.
Sharif said the opposition coalition had three demands: that the 1973 Constitution be restored, that the amendments to the constitution made by Musharraf not be recognised and that free and fair elections be held.
Bhutto said she believed their absence from the political stage was playing into the hands of parties exploiting religious and ethnic sentiments and that the only way to ensure a moderate Pakistan was to restore a pluralistic democracy.
"The issue really is: where does Pakistan go in the future? Is democracy, which has been promoted by the United States and the international community as a way to undermine terrorism, going to be applied to Pakistan or not?" she said.
"We believe that if this (political) vacuum continues then a moderate Pakistan will be very difficult to achieve."