Dozens of disgruntled Palestinian police officers stormed parliament building, complaining they don't have enough firepower to confront Hamas.
Politicians also, upset over the growing chaos demanded Palestinian leader Mahmoud Abbas reshuffle the cabinet and fire his security chief.
The protest and parliament's rebuke of Abbas came a day after the worst fighting between Hamas and police in nearly a decade.
Three people were killed, including the deputy police chief in the Shati refugee camp near Gaza City who was shot in the head after he and his men ran out of bullets during a Hamas assault on their station.
The violence underscored the difficulties Abbas and his ill-equipped security forces face in trying to take control of unruly Gaza.
Since Israel's pullout from the coastal territory last month, the Islamic militant Hamas has become increasingly brazen in challenging Abbas.
Israel and the United States demand that Abbas disarm Hamas. Instead, he has settled for a ban on displaying weapons in public, and has tried to coax gunmen off the streets with promises of jobs and political participation.
After the most recent onslaught on his security forces, Abbas said he would stand firm.
"We will not remain silent in the face of this," he told reporters at his Gaza City office. "This mob behaviour, this chaos must end."
The authority, he said, is "ready to use all means to prevent the public display of arms".
However, Palestinian security officials say police are no match for the armed groups.
In Gaza, only about half of the 18,000 members of the security forces carry guns, with a limited number of bullets at their disposal, the officials say. Hamas in Gaza commands at least 5,000 gunmen, according to some estimates, and has equipped them not only with assault rifles, but also with anti-tank missiles and grenades.