" Israel expresses sorrow for those killed in the takeover," the Israeli Cabinet said in a statement, according to one Hebrew-language website.
Israeli television, citing foreign media reports, said the death toll could be as high as 16.
"The images are certainly not pleasant. I can only voice regret at all the fatalities," Trade and Industry Minister Binyamin Ben-Eliezer told Israel's Army Radio.
The Israeli military said its soldiers were attacked with knives, clubs and other objects when they boarded one of the vessels. A military spokesman said protesters grabbed a commando's weapon and soldiers came under fire. But protest organizers insisted they were unarmed.
Protest organizers described a chaotic early-morning takeover in international waters.
A flotilla spokeswoman, Greta Berlin, told Israel Radio that the confrontation was broadcast live from a Turkish boat participating in the flotilla. The footage, she said, clearly showed Israeli soldiers landing on the deck and opening fire on civilians.
"The minute their feet hit the deck, they started to shoot," Berlin said.
She added, "Something happened to your country to make it think it is all right" to shoot civilians.
Israel Defense Force sources told Ynet, a popular Hebrew-language website, that the "organizers were not innocent — they demonstrated violence against the soldiers. They were prepared for their arrival."
Israeli radio military analyst Yoav Limor blamed the military for underestimating the resistance it would encounter. "There was serious violence" that forced the soldiers to open fire, he said.
Video images released by the protesters appeared to show passengers beating commandos with clubs as the soldiers rappelled onto the vessel's deck. A live video feed, which showed bloodstains and injured people, was abruptly cut.
The Turkish government issued a statement that "strongly protested" Israel's military action, according to Associated Press. The interception on the convoy is "unacceptable.... Israel will have to endure the consequences of this behavior," the statement read.
Turkish media reported angry protesters shouting "Damn Israel!" outside the Israeli Consulate in Istanbul.
Israel put its security forces on alert in case of demonstrations by the nation's Arab minority.
Flotilla organizers say they were carrying first-aid supplies and medical professionals in the event of casualties, but Adam Shapiro, the husband of one flotilla leader, said that "we thought that the possibility that Israeli soldiers would shoot" was remote.
Flotilla organizers said they carried no weapons.
The six-vessel flotilla, packed with hundreds of international activists, food and other humanitarian supplies, had left Cyprus on Sunday night in an attempt to break Israel's longstanding blockade of the Gaza Strip.
Israel had vowed to intercept the boats, by force if necessary, and tow them to the Israeli port of Ashdod, where passengers would be arrested or deported.
Israel says the blockade of Gaza, which is controlled by the armed Palestinian group Hamas, is needed to combat terrorism.
It's not the first time activists have attempted to break the Israeli blockade. Previously, protest ships have been turned back, escorted to Israel or allowed to pass through to Gaza. But the current flotilla, organized by Free Gaza and other pro-Palestinian advocacy groups, presented a greater challenge due to the sheer number of people — as many as 800 — taking part.
Batsheva Sobelman of The Times' Jerusalem Bureau contributed to this report.