Nicolas Madsen speelde in de jeugd van BK Marienlyst, Næsby BK en FC Midtjylland. Hij debuteerde in het eerste elftal van Midtjylland op 26 september 2018, in de met 1-2 na verlenging gewonnen bekerwedstrijd tegen Dalum IF. In het seizoen erna, 2019/20, kwam hij in het reguliere seizoen tot drie invalbeurten. In de kampioensronde, waarin Midtjylland een ruime voorsprong verdedigde, speelde Madsen ook enkele wedstrijden als basisspeler. In het seizoen 2020/21 begon hij als vaste basisspeler, speelde in de Champions League, maar raakte deze basisplaats gedurende het seizoen kwijt. Zodoende werd hij in het seizoen 2021/22 verhuurd aan sc Heerenveen.[1] Hier debuteerde hij op 12 september 2021, in de met 1-1 gelijkgespeelde uitwedstrijd tegen FC Groningen.
Op 20 juli 2022 tekende Nicolas Madsen een vierjarige contract bij Belgische Eersteklasser KVC Westerlo.
Denemarken
.svg){kind=small}
KVC Westerlo
Eredivisie