Madsen maakte in 1987 zijn debuut voor Holstebro BK maar stapte na een seizoen al over naar Ikast FS waar hij bleef spelen tot in 1991. Nadien ging hij aan de slag bij Odense BK waar hij bleef spelen tot in 1995 nadien speelde hij nog voor Vejle BK en Aarhus GF.