The 2004 battle of Fallujah - an unsuccessful military assault in which an estimated 27 U.S. Marines were killed, along with an unknown number of civilians - was retaliation for the killing, maiming and burning of four Blackwater guards in that city by a mob of insurgents.
Tens of thousands of foreign private security contractors work in Iraq - some with automatic weapons, body armor, helicopters and bulletproof vehicles - to provide protection for Westerners and dignitaries in Iraq as the country has plummeted toward anarchy and civil war.
Monday's action against Blackwater was likely to give the unpopular government a boost, given Iraqis' dislike of the contractors.
Interior Minister Jawad al-Bolani called the shootings "a crime that we cannot be silent about."
Many of the contractors have been accused of indiscriminately firing at American and Iraqi troops, and of shooting to death an unknown number of Iraqi citizens who got too close to their heavily armed convoys, but none has faced charges or prosecution.
"There have been so many innocent people they've killed over there, and they just keep doing it," said Katy Helvenston, the mother of Steve Helvenston, a Blackwater contractor who died during the 2004 ambush in Fallujah. "They have just a callous disregard for life."
Helvenston is now part of a lawsuit that accuses Blackwater of cutting corners that ultimately led to the death of her son and three others.
The question of whether they could face prosecution is legally murky. Unlike soldiers, the contractors are not bound by the Uniform Code of Military Justice. Under a special provision secured by American-occupying forces, they are exempt from prosecution by Iraqis for crimes committed there.
Khalaf, however, denied that the exemption applied to private security companies.
Iraqi police said the contractors were in a convoy of six sport utility vehicles and left after the shooting.
"We saw a convoy of SUVs passing in the street nearby. One minute later, we heard the sound of a bomb explosion followed by gunfire that lasted for 20 minutes between gunmen and the convoy people who were foreigners and dressed in civilian clothes. Everybody in the street started to flee immediately," said Hussein Abdul-Abbas, who owns a mobile phone store in the area.
Associated Press writers Qassim Abdul-Zahra in Baghdad and Matthew Lee in Washington contributed to this report.