Madsen started his career at BK Avarta in the secondary Danish 1st Division league, where he won the 1994 Danish 1st Division Revelation of the Year award. He was introduced to the top-flight Danish Superliga championship, when he was brought to newly promoted club Akademisk Boldklub in June 1996. Under manager Christian Andersen, AB finished fifth in the 1997–98 Superliga season, with Madsen on the left flank, combining well with teammate Peter Knudsen in central midfield. In June 1998, Madsen and Peter Knudsen were both brought to Italian club AS Bari in a combined transfer deal worth DKK 15 million. When they were forced to compete for the same spot in the Bari starting line-up, Peter Knudsen quickly returned to AB, while Madsen stayed three years at Bari. He started out well for the club, but was eventually benched by manager Eugenio Fascetti. Bari was relegated after the 2001 season, and as his Bari contract ran out in June 2001, Madsen left the club. He moved to German club VfL Wolfsburg on a free transfer. In the opening weeks of the German Bundesliga championship season, Madsen suffered a back injury, and struggled the remaining season to re-enter the starting line-up under manager Wolfgang Wolf without success. Following three league games for Wolfsburg, Madsen moved back to Denmark to play for Superliga club Farum BK under his former AB manager Christian Andersen in September 2002. Following one season at Farum, Madsen did not get his contract prolonged, and decided to take a job in the sales department of SAV Danmark in July 2003. After a month away from football, he started playing for amateur club HIK in the Danish 2nd Division in August 2003. He helped the club win promotion for the 1st Division, which saw the club turn professional, before he moved to league rivals Lyngby BK in November 2005. Due to an injured knee, he was forced to end his career in February 2007. Shortly after the news of his career stop, it was announced that he was to be associated with the newly founded Birkerød Sports College as a football coach, beginning in the summer of 2007. However, he chose to be new head coach at HIK. He only kept this job for a few months, because in June 2007 he was announced new sporting director at BK Fremad Amager. When his new club fired Jakob Friis-Hansen in May 2008 he became caretaker manager. After the season, he became manager of FC Amager. He had the job at Amager until March 2009, when the club went bankrupt. In June 2009 he was named the new manager of Vanløse IF. On 6 October 2011, he announced that he would not renew his contract with Vanløse, when it ended on 31 December 2011. In January 2012 he became assistant manager of Brønshøj Boldklub. He succeeded Erik Rasmussen as manager of Greve Fodbold on 1 January 2013. In January 2018 he became new manager of Akademisk Boldklub.
