Hamas and Islamic Jihad, the militant Palestinian groups, announced a three-month halt to attacks. After a day of internal bickering, Al Fatah, Yasir Arafat's mainstream faction, followed tonight with its own six-month cease-fire. 

The factions set several conditions for Israel, including a halt to its killings of accused terrorists and a release of Palestinian prisoners.

Though as skeptical as the Palestinians, Israelis hoped today that they might be entering a period of calm, or even nearing the end of what some Israeli commentators called, perhaps prematurely, "the thousand-day war," a reference to the 33-month conflict. Officially, however, Israel dismissed the cease-fire as a dodge to safeguard terrorists. 

Mahmoud Abbas, the Palestinian prime minister, had pursued the truce as a way to re-establish Palestinian security control without having to combat Hamas immediately, fearing that he lacked political support for that confrontation. He hopes that his support will grow as the Israelis relinquish what by previous agreement are Palestinian-controlled areas of the West Bank and Gaza Strip.

"It's a beautiful feeling," said Fawzi Abu Jarad, 30, a local resident. He stood among a knot of men here tonight, solemnly watching as Israeli soldiers used chains and a hydraulic lift to hoist four waist-high concrete cubes that were blocking a road and load them onto a flatbed truck. "Our goal is not to see any occupation forces here, not to see any Israeli soldiers," he said.

There was none of the jubilation — none of the handshakes or hugging of soldiers — that accompanied Israel's withdrawal in 1994 from much of Gaza under the Oslo peace accord. This time, the Palestinians, like the Israelis, know from hard experience how quickly the fighting could start again and the soldiers and concrete blocks could return.

From the cockpit of an armored vehicle, a couple of soldiers waved before accompanying the truck toward a nearby military base at about 11:30 p.m. 

A lone, giant Merkava tank that was still blocking Salahadin Road, the major east-west artery here, then spun around and followed, its treads clanking and the glare of its white spotlight splintering in the dust-filled air, as though in a fog.

An element of theater accompanied tonight's withdrawal. Their M-16's were at the ready, but the Israeli soldiers were nevertheless unusually indulgent of Palestinian cameraman, who swarmed around them and their armored machinery. In the glow of their own camera lights, the journalists pursued the Merkava down Salahadin Road, pursued in turn through the shadows by a few Palestinian boys, one of them waving a Palestinian flag.

The journalists noticed the boys. Their bubble of light stopped, then moved rapidly in the other direction until it enveloped the children and the cameras could come to bear on the green, red, black and white flag.

Though troops had sporadically raided this area of northern Gaza for months, they had been stationed here for only about 35 days, residents said. Israel said its soldiers were trying to prevent Hamas from continuing to fire crude rockets over Gaza's fenced boundary at Israeli towns. 

Tonight, the army left behind a trampled landscape of uprooted orange orchards, smashed sewer lines and demolished houses.

The withdrawal from Beit Hanun was the first joint step under the terms of an international peace plan known as the road map, a step negotiated on Friday in anticipation of the truce. Muhammad Dahlan, the Palestinian security minister, and Amos Gilad, an Israeli general, agreed on how to begin putting the plan into action in Gaza. Field commanders met today to work out further details in the kind of pragmatic, face-to-face discussion that peace negotiators hope will rebuild trust.

A senior Israeli military official said Israel intended to move quickly to comply with its commitments, withdrawing more troops and easing travel restrictions on Palestinians by Monday or Tuesday.

Palestinian security forces began moving in tonight to assume responsibility for stopping rocket fire and other attacks on Israelis, should the cease-fire be violated. Palestinian and Israeli officers also plan to resume joint security patrols along Gaza's main north-south road. 

Israeli forces will retain a large presence in Gaza, guarding the 7,000 Jewish settlers who live in several enclaves, among more than 1.2 million Palestinians.

While insisting on its own good will, each side said tonight that the new peace effort would succeed only if the other side abided by its commitments in the peace plan.

"These are important steps, and they pave the way for further progress on the road map," said Ziad Abu Amr, a Palestinian minister involved in negotiations with Hamas. "We hope Israel will not spoil it for us this time."

Gideon Meir, a senior official of Israel's Foreign Ministry, said: "Tomorrow there will be a new horizon. But success depends on the commitment of the Palestinian Authority to fighting terrorism."

In Washington, the White House said in a statement, "Anything that reduces violence is a step in the right direction." But it added: "Under the road map, parties have an obligation to dismantle terrorist infrastructures. There is more work to be done." 

The cease-fire and Israeli withdrawal came as Condoleezza Rice, President Bush's national security adviser, wrapped up two days of talks with Palestinian and Israeli leaders to promote the peace plan. The plan seeks to establish a Palestinian state and a comprehensive Arab-Israeli peace within three years.

In a meeting today with Prime Minister Ariel Sharon and his cabinet, Ms. Rice criticized a barrier fence that Israel is building against West Bank Palestinians. The barricade is being built generally along or to the east of the West Bank boundary, through Palestinian areas, and it jogs deep inside the West Bank at some points to encompass Jewish settlements.

Israel occupied the West Bank and Gaza Strip in the 1967 war, and since then it has settled more than 200,000 citizens there in a bid to hold on to the land. Palestinians regard the fence as a land grab.

Ms. Rice said the fence looked like a unilateral border, according to Israeli officials. But Mr. Sharon said it was strictly a security barrier, and officials indicated that construction would continue. 

"In Israeli society, there's a broad consensus that the fence is a necessity to protect our citizens from suicide bombers," said Raanan Gissin, Mr. Sharon's spokesman. "As the prime minister said, we won't compromise on security issues."

The White House statement said that Ms. Rice had reiterated an invitation to Mr. Abbas from Mr. Bush to visit Washington, but that no date had been set.

Many previous peace efforts have been greeted by surges in violence. But this time, the pledges by the three Palestinian factions to suspend violence raised the possibility of a sustained period of calm.

"We declare that military operations against the Zionist enemy will stop for three months, starting from today," Hamas and Islamic Jihad said in a joint statement released in Gaza. 

Al Fatah had sought the truce from the other groups, but in the end top officials of the faction balked in a dispute that stemmed at least partly from jealousy that Marwan Barghouti, a rising Fatah leader imprisoned by Israel, was receiving much credit for brokering the truce. Several Palestinian experts said Mr. Arafat was signaling that he remained in charge.

In the end, it was Mr. Arafat's office that gave the order tonight to Samir al-Mashharawi, a top Fatah official in Gaza, to release Al Fatah's statement. 

While acknowledging that jealousy of Mr. Barghouti had played a role, Mr. Mashharawi said Fatah members were upset about the wording in the Hamas statement. 

"Hamas said that resistance was the only strategy for them," he said in an interview in his Gaza City office tonight that was interrupted by the order from Mr. Arafat. "Fatah doesn't see it that way. For Fatah, all choices, including negotiation, are open."

Hamas and Islamic Jihad, which have always opposed peace negotiations with Israel, set no time frame for Israel to meet their demands, but said that if it failed to do so, "the enemy will bear the responsibility of what will result." 

Mr. Gissin, Mr. Sharon's spokesman, put no stock in the militants' pledge. "We deal only with the Palestinian Authority," he said. "And for us, there is only one proper response concerning the terror organizations: They have to be completely disarmed and dismantled. We will not accept anything less."

Another faction, the Popular Front for the Liberation of Palestine, said it would not join the declaration but would not violate the truce, according to Palestinian officials. 

The senior Israeli military official who spoke of further planned troop withdrawals said that Israel still had dozens of active warnings about possible Palestinian attacks and that instructions to halt violence had not filtered down through the Palestinian ranks. But he said Palestinian security forces in the West Bank had stopped at least two planned attacks against Israelis in recent days.

Alongside the simmering anger of Gazans at Israel is a sense of exhaustion with a conflict that has brought them a great deal of pain. The rockets fired from here by Hamas have, in a sense, wound up doing far more damage in Beit Hanun than in Israel, by giving Israel what many Palestinian considered a pretext to invade.

Among those quietly watching the Israelis depart tonight was Tawfik Bansh, 25. "My brother was killed here," he said. 

He said his brother, Rafik, 20, had been trying one night to sneak into Israel without a work permit. Watching the Israelis leave, Mr. Tawfik said, "I'm happy, because I don't want to lose another brother."