Hundreds of prisoners have been freed in a complex deal between Israel and the Lebanese militant group, Hezbollah.
Prisoners waited on buses until the German exchange was confirmed
Each side sent detainees to an air base in Germany, where identities were checked before Israel gave the signal for a mass release of Palestinians.
A second stage of the prisoner exchange is awaiting moves by both sides.
The swap in Cologne followed three years of talks and went ahead despite a suicide bus bombing in Jerusalem that killed at least 10 people.
There has been criticism from some Israeli politicians, who say it could strengthen militant groups and encourage future kidnappings, and complaints from the Palestinian side that most prisoners released in the deal were scheduled to be freed soon anyway.
Key among those released was a prominent Hezbollah leader, Sheikh Abdel Karim Obeid, who had been held by Israel for 15 years.
The BBC's Middle East analyst Roger Hardy says Israel is always ready to recover its citizens or their remains from captivity, but is paying a heavy price.
"Many Arabs credit Hezbollah with forcing Israel out of southern Lebanon almost four years ago. The prisoner exchange will be seen as a Hezbollah victory at a time when the Arab world has little to feel pleased about," our correspondent says.
The swap began with Israeli officials confirming that three bodies delivered by Hezbollah were those of missing soldiers Adi Avitan, Benyamin Avraham and Omar Sawayed who were captured near the Lebanon border in October 2000.
Hezbollah confirmed for the first time that the three soldiers were dead in a television broadcast on Wednesday night.
The guerrillas also released kidnapped Israeli businessman, Elhanan Tannenbaum, who arrived in Cologne on the same flight as the soldiers' remains.
About 35 Arab detainees and a German citizen, who had been jailed in Tel Aviv on spying charges, also arrived in Germany which helped to broker the deal.
The former prisoners later boarded flights to Tel Aviv and Beirut to return to their respective homes.
The BBC's Kim Ghattas in Beirut says a large celebration is planned at the city's airport to welcome the Lebanese contingent.
In Israel, Palestinian prisoners had been held on buses, to be released after official confirmation that the Cologne exchange had gone ahead.
Many kissed the ground as they reached checkpoints into the Palestinian areas of Gaza and the West Bank where cheering relatives awaited them.
But some said they had left behind them a sense of disappointment in the prisons.
Mussa Qattash, 22, who was in jail for more than two years for hurling a fire bomb at an Israeli car, said fellow inmates cried when they learned they were not among those to be released.
Israeli prisons hold about 7,500 Palestinians, the majority detained during the three-year uprising against the occupation in the West Bank and Gaza Strip.
"They considered it their last and only chance to be freed," he was quoted as saying by the Associated Press news agency.
Another man, Annam Sayel, 20, who was also jailed for throwing petrol bombs and stones at soldiers, complained at Israel's choice.
"Most of those freed were due to be freed in a few months' time anyway," he told Reuters news agency.
Further prisoner exchanges are yet to be agreed between Israel and Hezbollah.
Israel said its aim in releasing the senior Hezbollah figures was to use them as bargaining chips for information about a missing airman.
Israel hopes news of Ron Arad will follow Mr Tannenbaum's release
Israeli navigator Ron Arad went missing after his plane crashed in Lebanon in 1986.
News of his whereabouts could be secured in return for the release of Samir Qantar, a Lebanese militant who has been held in Israeli jails since 1979.