Israel freed nearly 200 jailed Palestinians on Monday - including a terrorist mastermind from the 1970s who became the Jewish state's longest serving Palestinian prisoner - in a goodwill gesture made hours before US Secretary of State Condoleezza Rice's latest peace mission to the region. At the start of her visit, Rice praised the Israeli gesture: "This is something that matters a lot to the Palestinians, it matters a lot to the Palestinian people and it is obviously a sign of goodwill." The prisoners received a hero's welcome upon their return to the West Bank, where thousands of people joined celebrations at the Ramallah headquarters of Palestinian Authority President Mahmoud Abbas and elsewhere throughout the West Bank. "We will not rest until the prisoners are freed and the jails are empty," Abbas told the cheering crowd. However, a moment of tragedy marred the joyous occasion when, according to the mayor of Yamoun, a crowded balcony gave way in the village, killing a nine-year-old girl and injuring 16 others. Relatives had crowded onto the rickety balcony to await the arrival of Muhammad Abahra, freed after eight years in prison. In Israel, the government came under fire for freeing Palestinian prisoners without receiving anything in return. Opposition leader Binyamin Netanyahu said that releasing the prisoners would weaken Israel and would not strengthen moderate Palestinians. "The crumbling Kadima government continues to demonstrate weakness that causes national humiliation," Netanyahu said. Transportation Minister Shaul Mofaz, who is running for leadership of the Kadima Party and who voted against the prisoner release in the cabinet last week, again voiced his opposition on Monday, saying Israel should only be freeing prisoners for captured soldier Gilad Schalit. "I ask: Why are we releasing prisoners with blood on their hands?" Mofaz said. "We will have to release prisoners for Gilad Schalit. We need more determined leadership that will know how to maintain the interests of Israel - and the interest of Israel is to release Gilad Schalit. For that we need to keep prisoners to use in exchange for him. Releasing prisoners now is a very big mistake." The prisoners arrived in Ramallah after being released at a military checkpoint near Jerusalem. The prisoners, some waving black-and-white checkered keffiyeh headdresses as they stepped off Israeli buses, kissed the ground before boarding Palestinian vehicles. Among the 198 Palestinians freed was Said al-Atba, who served 31 years of a life sentence for masterminding a 1977 market bombing that killed one woman and wounded dozens of others in Petah Tikva. Al-Atba, 57, was the longest serving Palestinian inmate in Israel and is widely seen by Palestinians as a symbol of all the prisoners. "I feel like I've been born again," al-Atba told The Associated Press. "This is a victory over the handcuffs," he added, but noted that thousands of prisoners remain behind. "We salute them and we must do all that we can to liberate them." His brother, Hisham, came from Saudi Arabia, where he works, to greet him. "I feel great, great joy," he said. "We had lost hope that my brother would be released because he's been in prison for 32 years." Al-Atba's sister, Raida, said she had prepared her brother's favorite food, stuffed grape leaves and zucchini. The fate of the roughly 9,000 prisoners in Israeli jails is emotional for Palestinians, many of whom know somebody behind bars or have themselves served time. Abbas, who is struggling to show his people the fruits of the peace talks, has repeatedly urged Israel to carry out a large-scale release. "It's not easy for Israel to release prisoners. Some of the individuals being released today are guilty of direct involvement in the murder of innocent civilians," Israeli government spokesman Mark Regev said. "We believe this action can support the negotiation process and create goodwill." Upon her arrival, Rice praised the Israeli gesture. "This is something that matters a lot to the Palestinians, it matters a lot to the Palestinian people and it is obviously a sign of good will," she said, calling on both sides to carry out more confidence-building measures. Rice, making her seventh trip to the region since peace talks were relaunched last year, has been trying to broker a peace agreement by the end of the year. Speaking to reporters on her plane, she acknowledged it was unlikely the sides would meet their year-end target, but said all sides remain committed to that goal. The talks have been complicated by Israeli political turmoil and Palestinian infighting. Prime Minister Ehud Olmert, who is battling a corruption investigation, has said he will step down after the Kadima party chooses a new leader next month. It remains unclear who his successor will be, and whether the government will be able to stay in power. On the Palestinian side, Hamas seized control of the Gaza Strip from Abbas's forces last year. Israel has said it will not carry out any peace deal until Abbas regains control over Gaza. Both Israel and the US have labeled Hamas a terrorist group. In the presidential compound in Ramallah hung a giant poster with pictures of Abbas, al-Atba and another veteran prisoner being freed, Mohammed Abu Ali, a lawmaker from Abbas's Fatah party. Abu Ali was jailed in 1980 for killing 20-year-old yeshiva student Joshua Saloma in Hebron and later convicted of killing a Palestinian in jail he accused of collaborating with Israel. In the festive Ramallah crowd was Abu Ali's wife Suad, 51, and the couple's three children: Ibrahim, 32, Palestine 29, and Leila, 27. "When Muhammad was arrested I was 22 years old, my children were babies," she said. "My family's life has begun today." Also among those freed were a 16-year-old girl who had been jailed for trying to stab an Israeli soldier and a young mother who had been incarcerated since January 2007 and had been raising a baby behind bars. She was sentenced for ties to Hizbullah. Wearing a long loose robe and a face veil, 30-year-old Khawla Zeitawi held her young daughter on her hip as she paused before the grave of Palestinian leader Yasser Arafat. Palestinians say 74 women are in Israeli jails. Israel has released prisoners to Abbas in the past, most recently last December. But it has balked at releasing Palestinians serving time for deadly attacks. It appears to be easing its criteria following a prisoner swap last month with Hizbullah. Under that deal, Israel exchanged Samir Kuntar, a Lebanese man convicted in a notorious triple murder, for the remains of two Israeli soldiers, Eldad Regev and Ehud Goldwasser. Eager to bolster Abbas in his rivalry with Hamas, Israel says the latest release is meant to show the Palestinians that dialogue, not violence, is the best way to win concessions. Hamas is demanding Israel free of hundreds of prisoners in exchange for Gilad Schalit, an Israeli soldier captured by Palestinian militants in a cross-border raid two years ago. Gil Hoffman contributed to this report.