The Israeli army lowered the flag over the Gaza Strip on Sunday before the first army convoys left Gaza after sundown.
Military jeeps and armoured bulldozers drove slowly through the Kissufim crossing point, marking the beginning of the end of Israel's presence in Gaza.
Palestinians nearby danced, played music and waved weapons and flags, and Palestinian security forces began entering the former Israeli settlements in the Gaza Strip in the early hours of Monday, a spokesman for the Palestinian Interior Ministry said.
The spokesman said hundreds of members of the national security service had entered seven settlements.
"The Palestinian flag has been planted in the settlements," Tawfiq Abu Khussa said.
Nearly 200 soldiers based in the Gaza Strip took part in the flag-lowering ceremony presided over by General Aviv Kochavi, commander of Israel's Gaza division.
"The withdrawal is going to start in several hours after the ceremony," an army spokeswoman said, confirming that there would be a final ceremony at the border between Israel and Gaza when the last troops leave.
A spokesman for the Israeli Defence Ministry said the last troops were expected to leave the Gaza Strip between 6am and 7am (0300 to 0400 GMT) on Monday.
But the final phase of the troop pullout was marred by disputes.
Israel had on Sunday cancelled a military handover ceremony after the Palestinians said they would not attend.
The Palestinians said they were staying away in protest against Israel's closure last week of a vital Gaza border crossing and a last-minute decision by Israel's cabinet not to demolish about two dozen synagogues in abandoned Jewish settlements in Gaza synagogues.
"As long as the border crossing is closed, we consider Gaza still occupied"
Sufian Abu Zaydeh,
Palestinian cabinet minister
"They throw these two problems in our faces, and it's really unfair," said Palestinian negotiator Saeb Erikat.
Israel said it was ending its 38-year military occupation of Gaza with the pullout; the last Israeli soldiers left the coastal strip by early Monday.
The troops erected a 100-metre wide security zone equipped with electronic detectors and landmines before the pullout, Aljazeera bureau chief in Palestine, Walid al-Omary, reported.
However, the Palestinians say that Israel will continue to control Gaza's airspace, territorial waters and border passages and that the occupation has not ended.
"As long as the border crossing is closed, we consider Gaza still occupied," said Sufian Abu Zaydeh, a Palestinian cabinet minister.
Saeb Erikat: Throwing these two
problems in our faces is unfair
In preparation for the Israeli pullout, 15,000 Palestinian troops were to deploy around abandoned Jewish settlements by early Monday to keep out large Palestinian crowds.
Security officials said they wanted to secure the area before allowing celebrations.
Also on Sunday, six Palestinians were wounded as Israeli troops guarding settlements in the Gaza Strip opened fire at crowds who had been throwing stones at their positions, medical sources said.
One of the victims was in a serious condition having been shot in the neck during the protests just hours before the Israeli
army's departure from Gaza.
Several hundred people had gathered near the walls of the main Gush Katif settlement bloc which were cleared of all Israeli residents some three weeks ago.
Witnesses said a group of youths had run towards Israeli tanks guarding the area when a tank opened fire.
Sunday's Israeli cabinet vote to end military rule over Gaza was largely symbolic because Israel has withdrawn all of its settlers 8500 settlers from Gaza, leaving only a small military presence.
But the unanimous decision finalised the withdrawal nearly two years after Prime Minister Ariel Sharon proposed the pullout.
Israel last week unilaterally closed the Rafah border crossing, the main gateway to the outside world for Gaza's 1.3 million Palestinians.
The Israeli cabinet voted on
Sunday to end military rule
Last week, Israel agreed in principle that foreign observers could eventually replace Israeli inspectors at Rafah.
However, Israel said that it could be months before the border reopens and that a final deal would depend on Palestinian willingness to crack down on resistance groups.
In the meantime, it plans to reroute border traffic through alternative Israeli-controlled crossings and turning over security control of the border to Egyptian forces.
Israeli officials on Sunday said it has completed its evacuation of the Rafah border crossing.
A spokesperson for the Israel Airport Authority (IAA), which operates the border crossing, said the most likely scenario is that a border crossing in the Negev called Nizana, which has served as a crossing for commercial goods, will be used to transport people until an agreement is reached on a more permanent crossing.
"It's a question of political issues and government issues.
"Our position is clear: We absolutely refuse that the current crossing be moved to anywhere else. If it is moved to Kerem Shalom, this will mean greater suffering for Palestinians"
Minister of Civil Affairs
"We are prepared to operate Nitzana [crossing] immediately - it served goods so far and might serve people also," said Orly Maman, spokesperson for the IAA.
At a press conference held on Sunday afternoon in Gaza City, Palestinian Minister of Civil Affairs Muhammad Dahalan blasted Israel's closing of the Rafah crossing.
"Our position is clear: We absolutely refuse that the current crossing be moved to anywhere else. If it is moved to Kerem Shalom, this will mean greater suffering for Palestinians.
"The crossing has to be fully Palestinian-Egyptian. We refuse any other proposal."
Palestinian Deputy Minister of Transportation Ali Shaath, who visited some of the vacated settlements on Sunday with representatives from the EU, remarked on the devastation he saw:
"Almost everything has been destroyed. Electricity lines have been cut, the water network has been shut off for several weeks, leaving a 'scorched earth'.
"Even trees that were carrying fruits such as date palms and olives have been uprooted."
But synagogues were left intact.
The Israeli cabinet voted to leave
20 Gaza synagogues intact
The Israeli cabinet voted 14-2 on Sunday against demolishing the synagogues in Gaza, even though many of the ministers previously approved the demolition as part of the pullout.
Critics said last-minute political considerations - including a desire to win the support of leading rabbis in advance of general elections - prompted several cabinet members to change their minds.
The Palestinians have detailed plans for the settlement areas, and the synagogues would be in the way.
"Symbols of the occupation have to be taken down," Hisham Abd al-Razaq, a Palestinian lawmaker, told Israel's Army Radio.
However, they fear international criticism if they demolish the buildings or if the structures are defaced by Palestinian crowds targeting symbols of occupation.
Cabinet Minister Haim Ramon said the rabbis are aware that the Palestinians will very likely knock down the buildings later on.
"They (rabbis) know the terrible consequences for Israeli-Palestinian relations if the Palestinians will demolish the synagogues," Ramon told Army Radio.
But Abbas national security adviser Jibriel al-Rajoub said the Palestinian Authority would not leave any building left over by the occupation, including synagogues.
Aljazeera.net's Laila El-Haddad contributed to this report from Gaza