The commission has been investigating allegations that Google manipulates its search results to favor its own services and products, such as specialized search services for hotels and restaurants or shopping, over those of rivals.
Under the February deal, which would have allowed Google to avoid fines of as much as $6 billion, the U.S. company agreed to present the results of three competitors in a comparable manner. The rivals would have to bid for the space in an auction.
Mr. Almunia asked Google this month to improve its settlement proposal for a fourth time. If Google fails to deliver the necessary changes, "the logical next step is to move to a statement of objections," or formal charges against the company, he said.
In a sign of the potential risks for Google, Mr. Almunia drew parallels with the EU's lengthy investigation of Microsoft Corp. MSFT +0.59% , which ultimately resulted in huge fines for the U.S. company.
"Microsoft was investigated [for] 16 years, which is four times as much as the Google investigation has taken, and there are more problems with Google than there were with Microsoft," Mr. Almunia said.
The decision to reopen settlement talks followed vigorous criticism from a widening range of politicians, including the economy ministers of France and Germany. The latter, Sigmar Gabriel, argued in May that a forced breakup of Google should be seriously considered because of its vast market power.