Alan Johnston was kidnapped near his Gaza home March 12, sending shockwaves through the Palestinian public and media, who have been pressing the government since to do more to win his release.
Security guards at the parliament building forced the angry reporters out, but the crowd threatened to stage similar protests at the headquarters of the Palestinian Authority and the Interior Ministry building.
On Sunday, leaflets claiming that Johnston had been executed by his captors were discovered in Gaza.
PNA officials, who unsuccessfully tried to negotiate Johnston's release March 13, said they could not confirm the claim, but vowed to do what they could to get the U.K. reporter back.
Johnston has been working in Gaza on a permanent basis for the past three years, and is now one of a handful of foreign journalists and aid workers abducted in the Palestinian enclave in the past two years.
On April 12, U.N. Secretary-General Ban Ki-moon also called for Johnston's immediate release.
In all previous cases, the victims were released unharmed after a few days.