Stefan Madsen először 2008-ban kezdett el dolgozni az Aalborgnál még másodedzőként, majd 2011 és 2013 között volt a német Leipzig vezetőedzője is, de 2015-ben újabb három évre visszatért az Aalborghoz.
A 47 éves szakember az Aalborg másodedzői posztja mellett a dán korosztályos válogatottaknál is tevékenykedett, de 2018-ban már vezetőedzőnek nevezte ki a klub.
Madsen irányításával az Aalborg háromszor lett dán bajnok, a legutóbbi két kiírásban viszont egyaránt elveszítette a GOG elleni bajnoki finálét, míg 2021-ben döntőig meneteltek a Bajnokok Ligájában, ám simán kikaptak a Barcelonától.
Stefan Madsennek eredetileg 2025 nyaráig szólt a szerződése, de végül úgy döntött, már nyáron elhagyja a csapatot.
„Az utóbbi időben megfogalmazódott bennem a gondolat, hogy próbáljak ki valami újat. Ez a gondolat egyre erősebb lett és most tettekké vált. Időnként mindenkinek új impulzusokra van szüksége, ez vonatkozik a klubra, a játékosokra és jelen esetben rám is” – mondta Stefan Madsen, aki egyelőre nem tudja, hol folytatja pályafutását.
„Stefan kétségtelenül a klub történetének legsikeresebb edzője. Három bajnoki cím, két kupa-, három Szuperkupa-győzelem és Bajnokok Ligája-döntő, szóval meg kell emészteni egy ilyen bejelentést. Mindezek ellenére megértjük és tiszteletben tartjuk a döntést, ahogy teljesen biztosak vagyunk abban is, hogy Stefan maximálisan elkötelezett lesz az idény hátralévő részében” – mondta Jan Larsen.