Condoleezza Rice, who postponed a trip to South Korea to push through the agreement, said, "It is a major step forward for the Palestinian people."
"This agreement is intended to give Palestinian people the freedom to move, to trade, to live ordinary lives."
The deal is seen as a key step toward the development of Palestinian autonomy and has the potential to revitalize the devastated Gaza economy.
The six-point agreement tackles land, sea and air travel and opens the Rafah crossing on Gaza's border with Egypt on Nov. 25.
Palestinians have long complained that isolation of the Gaza Strip has hindered any type of economic recovery, but Israelis were not willing to lift restrictions until measures were established to prevent weapons smuggling into Gaza from neighboring Egypt.
"We found solutions both sides can live with," said Mark Regev, a spokesman for Israel's Foreign Ministry. "The challenge was to find a successful balance between the very real security threats faced by Israel, while providing maximum movement in and out of Gaza for the Palestinians. I think it's a win-win agreement."
Israel has controlled the Rafah crossing since capturing Gaza from Egypt in the 1967 Arab-Israel War. After Israeli troops withdrew from the Gaza Strip in September, it was opened, but soon closed after Israeli security officials said large quantities of weapons were brought into Gaza during that period.
The sticking point was how Israel would ensure that militants were not using the passage as a way to build up weapons. Israel wanted to set up cameras to track travelers -- though Israeli security officials will not be present at the crossing.
The Palestinians were not happy with the cameras but under a compromise formula, European Union monitors helping to run the border will receive the video feed from the Palestinians, and then pass it on to the Israelis.
Israel also wanted to create a list of Palestinians barred from coming and going from Gaza. Under the negotiated terms, the Palestinian Authority agrees to consultations, "which will not take more than six hours," with the Palestinian Authority having final say on whether "to prohibit travel or not."
Rice reportedly led the arduous all-night negotiations from her ninth-floor suite in the David Citadel Hotel in Jerusalem, just outside the walled Old City.
She, along with James Wolfensohn, the former World Bank president and special Middle East peace envoy, and Javier Solana, the external affairs envoy for the European Union, worked with top aides to Ariel Sharon, the Israeli prime minister, and Mahmoud Abbas, the president of the Palestinian Authority.
Rice said one of the key details was Israel's promise to allow Palestinian farmers to export their current harvest, which will greatly improve the territory's economic viability.
The agreement also calls for the establishment of Palestinian convoys between the West Bank and Gaza, which will be escorted by Israeli security. Bus convoys are to begin by Dec. 15, and truck convoys are to start by Jan. 15.
The Palestinians may begin construction on a seaport on the Mediterranean coast, but no agreement was reached on reopening the Palestinian airport, which Israel destroyed when the Palestinian uprising began five years ago.