The CNIL, known within privacy and data protection circles as an aggressive and determined agency, also published a dozen "recommendations." Members of the Article 29 Working Party, a group of data protection officials from each member states, said the 27 European authorities have "unanimously adopted the findings of the audit."
Included in the recommendations, the CNIL suggested Google should strengthen the consent sought for combining data for the purposes of service improvement and advertising; provide a centralized opt-out solution; and adapt the combination rules to distinguish between security and advertising.
Google was also warned for not clarifying how long it stores user data for, otherwise known as data retention.
CNIL president Isabelle Falque-Pierrotin said Google has "not demonstrated its commitment" to the principles of the European Data Protection Directive, which governs the rules of data transfer and storage across the 27 European member states.
She added that it was "not the goal to declare war on Google and stifle innovation," but it was the CNIL's role to remind the search giant of its "responsibilities."
The Article 29 Working Party has given Google three to four months to comply with the CNIL's recommendations.
Google generates more than 96 percent of its annual revenues from advertising, according to last year's end of year financial statement.
While Google ran advertisements on subways and warned users each time they visited a Google service that the new policy was on the way, privacy groups criticized the move as users could not opt-out of the policy without the user pulling the plug on the service altogether.
However, European data regulators warned Google to put the changes on ice after they claimed the new policy may breach European data protection laws. Google said the raising of concerns as a "surprise," and pushed ahead with its March 1 deadline.
The CNIL was charged with investigating the search giant to determine whether or not Google had fallen foul of EU data and privacy laws. The outcome was initially expected in September.
On Monday, a coalition of 24 of the 27 member states' data protection agencies sent a letter to Google chief executive Larry Page asking the search giant to explain its intentions and detail how the firm shares data across its array of services.
The letter also said Google must seek "explicit consent" from its users when combining data across its services.
Update at 11:30 a.m. BST: with Google statement.