A fourth company was not fined because it revealed the existence of the cartel, the Commission said.
Campine, Eco-Bat Technologies, Recylex and Johnson Controls took part in a cartel from 2009 to 2012, fixing the price of scrap lead-acid car batteries bought from scrap dealers and collectors in Belgium, France, Germany and the Netherlands.
The case was unusual, the Commission said, in that most cartels collude to increase their sale price rather than lower the price at which they buy.
"By coordinating to lower the prices they paid for scrap batteries, the four companies disrupted the normal functioning of the market and prevented competition on price," it said.
"This behaviour was intended to lower the value of used batteries sold for scrap, to the detriment of used battery sellers. The companies affected by the cartel were mainly small and medium-sized battery collectors and scrap dealers," the Commission said.
Contact between the cartel members was mostly bilateral, via telephone calls, emails and text messages, with some multilateral meetings in person, it said.
"The parties were well aware of the illegal character of their contacts and sometimes tried to disguise them by using coded language, for example referring to weather conditions to signal different price levels," the Commission said.
Fines for cartels are usually set based on the value of sales. In this case, the Commission had to use the value of purchases, "which were presumably artificially lowered precisely because of the cartel behaviour", it said. An extra 10% was therefore added to the fines.
Eco-Bat and Recylex both had their fines reduced as they cooperated with the investigation, while Johnson Controls was given full immunity for revealing the existence of the cartel, avoiding a fine of €38,481,300.
Campine was fined €8,158,000, Recylex €26,739,000 and Eco-Bat €32,712,000.
Commissioner Margrethe Vestager, in charge of competition policy, said: "Well functioning markets can help us reduce waste and support the circular economy. Therefore, we do not tolerate behaviour that undermines competition. The four companies fined today have colluded to maximise their profits made from recycling scrap batteries, reducing competition in this essential link of the recycling chain."
Automotive batteries are the world's most recycled consumer product, the Commission said, with almost 99% of car batteries in the EU being recycled. Around 58 million automotive batteries are recycled in the EU every year.