Maria Kliegel a Nelson Mandela mały|Maria Kliegel i Nelson Mandela w jego rezydencji W 1995 roku, poruszona po lekturze autobiografii Nelsona Mandeli, Maria Kliegel postanowiła znaleźć drogę do złożenia mu hołdu poprzez muzykę poważną. Tak zrodził się pomysł stworzenia utworu Hommage à Nelson M. na wiolonczelę i perkusję. Dzięki połączeniu tych instrumentów Maria Kliegel chciała zbudować muzyczny pomost między europejską tradycją muzyczną a natywnym poczuciem rytmu czarnej ludności RPA. Po skontaktowaniu się z kompozytorem Wilhelmem Kaiser-Lindemannem i przedstawieniem mu tej idei, znalazła w nim sprzymierzeńca. Celem ich obojga stało się doprowadzenie do premiery utworu w RPA z Mandelą jako gościem honorowym.
Dzięki przyjaźni z ówczesnym prezydentem Nadrenii Północnej-Westfalii i późniejszym prezydentem Niemiec Johannesem Rau, udało jej się przekazać list do Mandeli podczas jego wizyty państwowej w Niemczech, informując go o powstałym pomyśle. W 1999 otrzymała Order Zasługi Nadrenii Północnej-Westfalii.
Ponieważ plany koncertowe w RPA nie mogły zostać skonkretyzowane, a artystka chciała jak najszybciej wysłać kompozycję jako przesłanie do świata, premiera odbyła się w grudniu 1996 r. przed bardzo poruszoną publicznością w Tonhalle w Düsseldorfie.