Rival Palestinian factions Fatah and Hamas have signed a deal to form a national unity government.
The deal follows months of faltering talks between the two sides
Palestinian Authority President Mahmoud Abbas and exiled Hamas political chief Khaled Meshaal signed the accord after talks in the Saudi city of Mecca.
It follows weeks of factional violence in Gaza and a year-long international embargo against the Hamas government.
Mr Abbas urged the new government to "respect" previous accords signed between the Palestinians and Israel.
AGREEMENT KEY POINTS
Ismail Haniya of Hamas remains PM
Key interior, finance and foreign ministries to be run by independents
Reports say Hamas to take nine cabinet posts, Fatah six and one each to four other parties
No explicit recognition of Israel
But reports said the text of the agreement contained no reference to formal recognition of Israel.
Hamas has consistently refused to recognise the Jewish state - a key demand of Western countries behind a crippling economic boycott of the Palestinian Authority (PA).
Following the signing, Israeli government spokeswoman Miri Eisin said the criteria to end the freeze had not changed.
"Israel expects a new Palestinian government to respect and accept all three of the international community principles - recognition of Israel, acceptance of all former agreements and renunciation of all terror and violence," she told the Associated Press news agency.
A spokesman for the US State Department told the BBC that Washington remained committed to President Bush's vision of two democratic states - Israel and Palestine - living side by side, and that the Palestinian people deserved a government that could pursue that goal.
But the BBC's James Westhead in Washington says the statement avoids any judgement, on the grounds that it has not seen the details of the composition or the political programme.
The BBC's Jon Leyne in Gaza says Fatah and Hamas have finally resolved their differences.
He says they have agreed a share-out of government posts, with independents taking the key jobs of finance, foreign affairs and the interior.
AFP news agency, citing a copy of the agreement, said Hamas would fill nine posts, six would go to Fatah and one each to four other parties in parliament.
Hamas Prime Minister Ismail Haniya will retain his position.
The first hope of all Palestinians will be that this will end the vicious fighting that has raged between Hamas and Fatah as recently as last weekend, our correspondent says.
The other key question, he adds, is whether Hamas has gone far enough to enable international sanctions to be lifted.
Mr Abbas and Mr Meshaal signed the agreement, named the "Mecca Declaration", at a ceremony hosted by King Abdullah of Saudi Arabia.
Mr Meshaal called for violence to stop immediately, describing the factional fighting and unrest in the Palestinian territories as "dark days".
"It is our turn to make this agreement work and to make this agreement stick, to build our Palestinian house on strong foundations," he said.
The news was greeted with unbridled joy in Gaza
He said the international community "must respect our accord, recognise our Palestinian reality and deal with it seriously".
Hamas and Fatah have been locked in a bitter power struggle since Hamas defeated Fatah in elections in January 2006.
Months of violence between Fatah and Hamas supporters left scores dead and Palestinian civilians frightened to venture on to the streets.
As the signing took place, celebratory gunfire erupted in Gaza City, while fireworks lit up the sky.
Gunmen who until a few days ago were shooting at each other are firing in the air in celebration, our correspondent says.
The streets which were deserted are now full of cars, crowds celebrating, people waving the flags, often of Hamas and Fatah simultaneously, he reports.
"For four or five days we've been holding our breath," Mahmoud Qassam, 27, a fish vendor, told AP news agency.
"God willing, this is a permanent agreement, not a temporary truce," he said.