The two journalists were dropped off at Gaza City's Beach Hotel by Palestinian security officials and appeared to be in good health. A tearful Centanni embraced a Palestinian journalist briefly as he entered, then rushed upstairs as Wiig followed.
Centanni, in a phone interview shortly after his release, said "I'm fine. I'm just so happy to be free."
He said he was so emotional because he was out and alive.
"There were times when I thought 'I'm dead,' and I'm not," Centanni said. "I'm fine. I'm so very happy."
Prior to their release, the kidnappers released another videotape.
Parts of the latest six-minute tape, aired on al-Jazeera television, showed Centanni and Wiig seated cross-legged. Both read from written statements condemning the American policy in the Middle East. In one scene, both men were shown eating.
"It is Apache helicopters firing Hellfire missiles made in America that kill the residents in Gaza," Wiig said on the tape.
Their statements were punctuated on the tape with screens of written verse from the Koran, and scenes from Abu Ghraib, the prison in Iraq that was the site of abuse of Muslim prisoners by American soldiers.
Despite this barbaric treatment, the two men still very positive towards the Palestinians.
At a news conference, Centanni and Wiig said they worried that their kidnapping might discourage other news organizations from reporting on the Palestinians, whom Centanni said "are beautiful."
"That would be a great tragedy for the people of Palestinians" if their story does not get told, Wiig said. "You guys need us on the streets."
The end of the FOX News story, which included material from the Associated Press, tries to put the kidnapping into perspective.
In chaotic Gaza, gunmen often change their affiliation or form splinter groups. Their agendas are often driven by personal issues, including jobs and power for their clans, rather than by ideology.
They sound almost like old-fashioned hillbillies. Except for the death worship and the blowing up of Jews.