Representatives from France, Germany, Italy, the Netherlands, Spain and Britain said on Tuesday they have kicked off a process to decide if Google's policy - introduced in March 2012 - broke national laws.
Google consolidated 60 privacy policies into one last year and started combining data collected on individual users across its services, such as YouTube, Gmail and social network Google+. It gave users no means to opt out.
Twenty-nine European data protection regulators engaged in a joint inquiry to investigate.
The inquiry, led by France's CNIL, found in October that Google's new policy posed a "high risk" to the privacy of individuals, but the findings stopped short of declaring it illegal.
Google had until February to propose changes, but none was forthcoming.
"Regulators in six states have begun the process of looking at penalties, and each must now act based on national law," said Isabelle Falque-Pierrotin, CNIL's president, in an interview.
"We have put in place a countdown for Google now. Promises to change will no longer be enough."
The six states have the power to impose fines on Google, said Falque-Pierrotin, but each must go through a local inquiry to determine that a wrong had been committed under national law even after the European joint position published in October.
The participants will use the joint analysis to underpin their investigations and will "not start from scratch", she added.
Google said it would continue to cooperate with European regulators.
The year-long tussle with the web search giant is seen by legal experts and policymakers as a test of Europe's ability to influence the behavior of international Internet companies.
Policymakers are debating a draft Europe-wide data protection law under which transgressors could be fined as much as two percent of their annual global turnover.
It would impose stricter rules on how companies collect and store customer data and would require notification of data breaches. The plan has sparked a lobbying effort by big technology companies, banks and other firms, anxious it would lumber them with additional costs.
Jacob Konhstamm, head of the Dutch data protection regulator, said the fact that each state had to take enforcement action separately showed the need for the new law.
"If anybody needed an argument that the directive should change, then this is it," he said in an interview.
A spokesman for Britain's Information Commissioner's Office (ICO) said it was likely to decide in the summer what action, if any, to take against Google. The highest penalty the ICO can impose is 500,000 pounds (A$723,00).
France's CNIL has filed its action against Google and the next likely step would be to notify the search engine that it is in violation of local law, giving it three months to respond before fines can be applied. The maximum fine is 300,000 euros.
Italy and Spain also confirmed in emailed statements that they have commenced local enforcement actions.
Privacy director leaves
In a internal announcement, Google said yesterday that it's privacy director, the London-based Dr Alma Whitten, is stepping down, having worked in that position since 2010.
First reported by Forbes, Whitten says she intends to retire from Google after a decade at the search engine giant. It is not known if Whitten's departure is related to Google's ongoing privacy blunders that have raised regulatory hackles around the world.
Whitten, a computer scientist and software engineer by training, will be replaced by Lawrence You who is stationed at Google's Mountain View, California headquarters.
(Additional reporting by Clare Kane in Madrid and Danilo Masoni in Milan; Editing by Tom Pfeiffer