Madsen maakte zijn debuut voor Brøndby IF in 1996 en speelde bij de ploeg tot in 2003 in die tijd won hij een beker en werd twee keer landskampioen. Hij werd uitgeleend aan het Duitse VfL Wolfsburg en vertrok definitief naar VfL Bochum. Hij speelde ook nog voor 1.FC Köln en werd uitgeleend aan het Engelse Southampton. Hij keerde terug bij Brøndby IF in 2007 en speelde er tot in 2012 gedurende deze tijd werd hij nog eenmaal uitgeleend nu aan Lyngby BK.
Hij speelde dertien interlands voor Denemarken en scoorde driemaal. Hij nam met de Deense ploeg deel aan het WK voetbal 2002.
Denemarken
·
6 Helveg ·
7 Gravesen ·
8 Grønkjær ·
9 Tomasson ·
10 Jørgensen ·
11 Sand ·
12 N. Jensen ·
13 Lustü ·
14 C. Jensen ·
15 Michaelsen ·
16 Kjær ·
17 Poulsen ·
18 Løvenkrands ·
19 Rommedahl ·
20 Bøgelund ·
21 Madsen ·
22 Christiansen ·
23 Steen Nielsen ·
Coach: Olsen