Egon Madsen nasce in Danimarca. Inizia a studiare danza con Thea Jolles, Birger Bartholin e Edith Frandsen. A dieci anni calca per la prima volta il palcoscenico come membro del Children's Ballet di Aarhus. Nel 1958 raggiunge il Tivoli Pantomime Theater di Copenhagen dove danza con lo Skandinavian Ballet. Dopo avere passato l'audizione con il Danish Ballet, nel 1961 Madsen raggiunge il Balletto Württembergische Staatstheater di Stoccarda, diretto da John Cranko, diventandone primo ballerino nel 1963.
A Stoccarda, Madsen ha fatto parte della storia del balletto, non solo per i tanti ruoli che sono stato creati su di lui, ma anche per essere diventato una delle personalità leggendarie dello sconosciuto Stuttgart Ballet che ha conquistato il cuore del pubblico e della critica internazionale.
Per quattro di loro: Richard Cragun, Birgit Keil, Marcia Haydée e lui, Cranko ha creato il balletto sulla musica sinfonica di Brahms intitolato con le loro iniziali :R.B.M.E..
Di incisiva personalità teatrale, si impone come uno degli interpreti favoriti di John Cranko, che per lui crea i ruoli di : Mercuzio in Romeo e Giulietta (1963), Lenski in Onegin (1965), il Joker in Jeu de Cartes (1965), Gremio in La Bisbetica Domata (1969), Don José in Carmen (1971), ed il Giovane in Poème de l'extas, ruolo che ha danzato con Margot Fonteyn.
Nel 1965 Kenneth MacMillan ha creato per lui il ruolo di Eternal One in uno dei suoi più famosi balletti Song of the Earth. Peter Wright ha creato su di lui il ruolo di Albrecht in Giselle, che successivamente è entrato a fare parte del repertorio delle maggiori compagnie del mondo. In seguito della morte di Cranko nel 1973, Madsen ha continuato a lavorare con il suo successore, il coreografo contemporaneo americano Glen Tetley, con cui ha lavorato per numerose creazioni fra cui Daphnis et Chloè (1975).
Dopo le dimissioni di Tetley nel 1976, Madsen continua a danzare a Stoccarda sotto la direzione di Marcia Haydée. Durante questo periodo sono stati creati con lui il Requiem di MacMillan, Hamlet di Neumeier, il ruolo di Armand Duval in La Dame aux camélias di Neumeier, con Marcia Haydée nel ruolo principale, Love Songs di William Forsythe. Come uno dei più famosi danzatori della sua generazione, Madsen è stato invitato come Ospite nelle maggiori compagnie del mondo, specialmente a Londra, New York e con il Royal Danish Ballet di Copenhagen.
Nel 1981, Madsen lascia lo Stuttgart Ballet per prendere la Direzione del Balletto di Francoforte. Nel 1984 è stato Direttore del Royal Swedish Ballet e nel 1986 è stato Direttore del Balletto del Teatro Comunale di Firenze. Dopo un breve periodo come danzatore maestro e coreografo free lance, nel 1990 viene nuovamente invitato presso lo Stuttgart Ballet da Marcia Haydée come ballet master, successivamente viene nominato come Vice Direttore dello Stuttgart Ballet. In seguito al ritiro di Marcia Haydée quale direttrice dello Stuttgart Ballet in 1996, Madsen raggiunge il Leipzig Ballet come Ballet Master Principale sotto la direzione del coreografo Uwe Scholz.
Nel gennaio 1999, Madsen, viene invitato da Jiri Kylian a fare parte del Nederlands Dans Theater III, nuovo gruppo creato con danzatori sopra i 40 anni. All'inizio della stagione 1999-2000, Madsen viene nominato Direttore Artistico, continuando la sua partecipazione agli spettacoli come danzatore ed ispirando ancora coreografi come Jiri Kylian, Robert Wilson, Mats Ek, Meryl Tankard and Paul Lightfoot. Dopo sette anni con il NDT III, Madsen da le dimissioni continuando a lavorare come danzatore e ballet master free lance, lavorando spesso con lo Stuttgart Ballet, il Norwegian National Ballet, il Balletto Nazionale del Cile, il Nederlands Dans Theater, la Compagnia Nazionale di Danza di Madrid ed il Vienna State Opera Ballet.
Ha inoltre insegnato presso: the Royal Conservatory di Den Haag, la Rotterdam Dance Academy e la scuola dello State Opera Ballet di Vienna. In ottobre ha debuttato nello spettacolo Don Q. coreografia di Christian Spuck.
