"The film equates Islam with violence. We reject that interpretation," said Balkenende said in a statement in Dutch and English, reported Agence France-Presse (AFP).
"We believe it serves no purpose other than to offend."
Geert Wilders, the leader of the right-wing Freedom Party, released his anti-Qur'an film on a video-sharing website on Thursday, March 27.
A Counter Movie Against Wilders' In Opposition to Anti-Qur'an Film
The film, entitled "Fitna," an Arabic word for sedition or strife, starts with a Danish cartoon showing a man described as Prophet Muhammad (peace and blessings be upon him) with a ticking bomb in his turban.
It then shows a page from the Qur'an on the right and a translation of one specific verse on the left.
The documentary then shows images of airplanes flying into the World Trade Centre in New York on September 11, 2001, with soundbites from phone calls to the emergency services on that day.
It continues with grisly images of bloodstained bodies in the aftermath of the Madrid train bombings in March 2004 in which 191 people were killed.
The film warns of the rising Muslim immigration in Europe and urges Muslims to tear out "hate-filled" verses from the Qur'an and ends with a someone turning a page of the Qur'an, with a sound of tearing at the background.
"The sound you heard was from a page being removed from the phonebook," says a text that appears on the screen.
"For it is not up to me, but to Muslims themselves to tear out the hateful verses from the Qur'an," it goes on.
Balkende said the Dutch government "regrets" the release of the anti-Qur'an film.
"But feeling offended must never be used as an excuse for aggression and threats," he said.
The government announced that the public prosecutor's office was investigating Wilders' film to see if it broke any laws.
"The Dutch government stands for a society in which freedom and respect go hand in hand... Let us solve problems by working together," said Balkende.
The government has unsuccessfully tried to convince to the right-wing lawmaker to abandon the film, fearing it would trigger protests in Netherlands and overseas and strain ties with Muslim countries.
Foreign Minister Maxime Verhagen told AFP that he had been in contact with Dutch embassies in the Muslim world but that so far there were no reactions being reported.
He added that he also informed the EU presidency of the film and the government's reaction to it.
The Dutch premier said that his government felt heartened "by the initial restrained reaction by Dutch Muslim organizations".
In initial reactions, Muslim organizations seemed relieved that the scenes from Wilders' film were not as bad as expected. Some feared Wilders would destroy a copy of the Qur'an in the film.
Dutch newspapers were also relieved at the mild reaction to the anti-Qur'an documentary.
"Relief over 'mild' Fitna," headlined the left-leaning Volkskrant adding that the film "was not as over the top as expected".
Christian paper Trouw summed it up as "Fitna offends but does not surprise", while the popular Algemeen Dagblad concluded "the book, the Qur'an, is better".
But the right-wing Telegraaf paper said that "Friday prayers are crucial".
"Neatly told but no incitement to hate," read the headline of the mass-circulation daily.
Dutch Muslim leaders have vowed a calm and wise handling of the crisis.
They have urged the minority, which makes up one million of the country's 16 million population, not to pay heed to a "third-class" politician like Wilders.
They have also decided to open mosques to non-Muslims to wash away the misconceptions propagated by Wilders and his alike.
