Geboren auf der Insel Fünen, Dänemark, sammelte Egon Madsen erste Bühnenerfahrungen mit dem Aarhus Kinderballet, es folgten Engagements beim Tivoli-Pantomimentheater und dem Skandinavischen Ballett. Zum Stuttgarter Ballett kam er 1961; dort ernannte ihn John Cranko schon ein Jahr später zum Solotänzer.
In Stuttgart schrieb Egon Madsen Ballettgeschichte, nicht nur durch die Vielzahl von Rollen, die John Cranko, Kenneth McMillan, Peter Wright und viele andere für ihn schufen, sondern auch als eine derjenigen Persönlichkeiten, mit denen das Stuttgarter Ballett die Bühnen der Welt eroberte. Unvergessen bleibt er nicht nur in Crankos Onegin, Schwanensee, Der Widerspenstigen Zähmung oder Poème de l’extase, sondern auch in vielen modernen Rollen etwa von Glen Tetley oder seines Kollegen John Neumeier. Zu seinen berühmten Partnerinnen zählten neben Marcia Haydée auch Margot Fonteyn, Gelsey Kirkland, Lynn Seymour, Eva Evdokimova, Anita Cardus und Lucia Isenring, mit der er seit 1980 verheiratet ist.
1981 übernahm Egon Madsen die Leitung des Balletts in Frankfurt, später wurde er Ballettdirektor des Königlich Schwedischen Balletts in Stockholm und anschließend am Teatro Communale in Florenz. 1990 holte ihn Marcia Haydée als Ballettmeister und späteren stellvertretenden Ballettdirektor zum Stuttgarter Ballet zurück; 1996 dann ging Egon Madsen als Erster Ballettmeister zum Leipziger Ballett unter der Leitung von Uwe Scholz.
1999 folgte Madsen der Einladung Jiří Kyliáns ans Nederlands Dans Theater III, einer Balletttruppe für Tänzer über 40 Jahre und kehrte nach langer Pause wieder auf die Bühne zurück. 2000 bis 2007 übernahm er hier die Künstlerische Leitung. Seit 2009 ist Egon Madsen Company Coach von Gauthier Dance, wo er seit 2007 mehrere Stücke von und mit Eric Gauthier erarbeitete. Darüber hinaus ist er als Gastdozent weltweit tätig.