Gilad Shalit, an Israeli soldier captured by Hamas five years ago, has been transferred to Israel authorities following an agreement with Gaza's rulers to a prisoner swap, local television has reported.
The 25-year-old soldier was initially handed to Egyptian mediators by Hamas on Tuesday before travelling to Israel.
Speaking to Egyptian television shortly after his release, Shalit described his capture: "I cannot describe my feelings at the time however I felt that I would be facing difficult times to come."
"Obviously i missed my family, a lot and also I missed my friends. I missed meeting normal people to talk to them to tell them about my experience ... in captivity.
Looking pale and overwhelmed by developments, he said he was informed of his release one week ago, and that Hamas had treated him well.
When asked about his thoughts on the Palestinians still held in Israeli prisons he said: "I will be very happy if all these prisoners are free."
"So that they can be able to go back to their families, loved ones and to their territory. It will give me great happiness if this happens."
He added that he hoped the prisoner swap between Israel and Hamas would "help the conclusion of peace".
"And I hope that cooperation, links between the two sides will be consolidated," he said.
Hassan Mousa, a Hamas leader in the West Bank, said the prisoner exchange was a "great day" for the Palestinian people.
"It has unified the Palestinian people together. It will free people who have been in Israeli jails more than 34 years and more that 30 years, and many more with high sentences and will free the women and children alike," he said.
Israeli prime minister Binyamin Netanyahu said it had been a "difficult decision" to agree to the prisoner exchange but it was the best decision he could make.
"It is very difficult to see these people who killed their dear ones being released before they completed their punishment," he said.
Earlier Israeli newspaper Haaretz reported that buses carrying Palestinian prisoners had rolled out, "in effective confirmation of Gilad Shalit's presence in Egyptian hands".
His release comes after five years in captivity, and after Israel made an agreement with Hamas to set 1,027 Palestinian prisoners free.
Speaking about the price Israel is paying for Shalit's freedom, former foreign secretary David Miliband told The Huffington Post UK that the release of suicide bombers could have a "considerable effect".
"I don't think that we can sit in judgement in that way. It's a remarkable commitment that Israeli governments make to their own solider that come hell or high water, if they're alive they'll try and rescue them.
"And it's born of particular history. It obviously stands in stark contrast to the position that other governments take in different circumstances. So I don't think it's for us to sit in judgement. What I think we have to recognise is it's both born of particular circumstances and has considerable effects beyond the simple trade of soldier for a large number of prisoners."
Some 477 Palestinians will be freed initially, followed by an extra 550 in the next two months.
Shalit's father Noam said this morning: "You can say this is one of the happiest days of my life."
Al Jazeera reported a "festive atmosphere" at the West Bank border crossing of Beitunia, with crowds waiting for Palestinian returnees waving flags and chanting slogans. Others are gathered at Rafah, the border town between Egypt and Gaza, the broadcaster said.
A number of the Palestinian returnees will be deported, with Turkey expected to taken in some of the prisoners, the state news agency Anatolia said on Tuesday.
However the deal is not without controversy. The families of four victims of terrorism on Monday failed in their bid to get the Israeli High Court of Justice to delay the release.
The Palestinian International Solidarity Movement has also questioned the move, saying that many of the freed prisoners will be sent to blockaded territory in Gaza.
In Israel, voices have been raised questioning the one-sided nature of the deal, suggesting that the Palestinian returnees could go back into active service. It has also been argued that such an influx will bolster Hamas, which holds power in the Gaza Strip, further isolating Palestinian moderates.
Hamas has agreed that around 200 of those due to be returned will be deported from Palestine, however this has failed to placate some Israelis, especially as many of those due for release carried out recent crimes.
Included on the list is Abdel Aziz Salha, who killed two soldiers in Ramallah in 2002; Ibrahim Younis, who is responsible for killing seven people in Jerusalem in 2003; and Nasser Yateima, who planned the bombing of a hotel, which killed 30 people in 2002.
Ahlam Tamimi, who killed 15 people in a cafe in Jerusalem in 2001, is also scheduled to be freed. Family members of one of her victims are also expected in court.
David Cameron welcomed the release of Shalit and said he hoped it would help the peace process.
"I can only imagine the heartache of the last five years, and I am full of admiration for the courage and fortitude which Sergeant Shalit and his family have shown through his long cruel and unjustified captivity," he said.
"I congratulate prime minister Netanyahu and everyone involved for bringing him home safely, and hope this prisoner exchange will bring peace a step closer."