Nestlé, the world's largest food company, became in 2012 the main sponsor of a programme organized by the IAAF aimed at promoting athletics for youths worldwide.
It was reported to be worth $1 million a year.
“Angered and dismayed by today's kids' athletics announcement. We will not accept it. It's the kids who will suffer,” said IAAF president Coe in a brief statement issued on Wednesday.
Nestlé said they were concerned over fears that the corruption and doping scandals surrounding the sport could damage the company's reputation.
“I confirm that we have decided to end our partnership with the IAAF Kids Athletics programme with immediate effect,” Nestlé spokeswoman Lydia Meziani told AFP in an email.
“This decision was taken in light of negative publicity associated with allegations of corruption and doping in sport made against the IAAF,” she added.
Meziani said Nestlé decided to “terminate (its) existing relationship with the IAAF” because a continued partnership “could negatively impact our reputation and image.”
The IAAF is facing crises on multiple fronts, including widespread allegations of corruption and bribery under disgraced former boss Lamine Diack.
Before Coe's tough-talking reaction to Nestlé's decision, the world body had been keen to stress the benefits of its partnership with Nestlé.
“The IAAF is in discussion with Nestle concerning the final year of its five-year partnership with IAAF Kids' Athletics,” said the IAAF in a statement.
“This has been a successful programme with 15 million kids aged seven to 12 years in 76 countries taking part in fun team activities which promotes a healthy, active lifestyle.
“In 2016 IAAF Kids' Athletics plans to reach a further 15 countries, training 360 lecturers, instructing 8,640 physical education teachers, with three million children participating by the end of the activation.”
Separately, Coe, an English former Olympic track star, has faced criticism following Russia's ban from the sport for what a commission of the World Anti-Doping Agency's (WADA) described as “state-sponsored” doping.
WADA's report claimed that the IAAF governing council must have known about corruption orchestrated by Diack, and about doping in Russia.
Since the scandals broke, Coe has been travelling the globe, notably in Asia, where he has sought to shore up support for IAAF, hoping to ease the concerns of corporate backers weary of being tied to a tainted organization.
Speaking in Tokyo on Monday, Coe, who won back-to-back Olympic 1,500 metres gold medals at the 1980 and 1984 Games, said “the journey back to trust is one of an uncertain length, but we have to make changes.”
Nestlé said it had informed the IAAF of its decision and would “await a formal acknowledgement from them that our partnership has ended”.
The defection of Vevey-based Nestlé as a sponsor came after the IAAF admitted last month that it was battling to retain corporate backing, amid reports that Adidas was also walking away.
The deal with the German sportswear giant signed in 2008 and reportedly worth tens of millions of dollars was due to run until 2019.
Independent investigations have found that corruption was embedded in the IAAF during the tenure of Diack, a Senegalese national now facing criminal charges in France.