Madsen played NCAA basketball at Stanford, where he finished his career ranked in the school's career top 10 in blocks and rebounds. In addition, Madsen helped the Cardinal to four NCAA tournament appearances, including a Final Four berth in 1998. Perhaps his signature moment at Stanford was his dunk and free throw that gave Stanford a lead over Rhode Island, propelling the team into the Final Four, where it lost to eventual champion Kentucky. Madsen was a two-time All-American and a two-time All-Pac-10 selection.
The Los Angeles Lakers selected Madsen in the first round (29th pick overall) of the 2000 NBA Draft. He contributed to the Lakers' NBA championships in 2001 and 2002, and became well known for his goofy dances at the victory parades for those championships.
Talking about his prime with the Lakers, Shaquille O’Neal said that the only player who could thwart him from his dominant play was Madsen. "He used to beat me up in practice”, O’Neal said.
Madsen signed with the Timberwolves as a free agent before the start of the 2003–04 NBA season. He played six seasons for the Wolves.
Following being waived, Madsen was hired as the assistant coach for the Utah Flash of the NBA Development League (D-League). In 2012, he was hired as an assistant coach at Stanford. On May 13, 2013, he was named head coach of the Los Angeles D-Fenders, a D-League team owned by the Los Angeles Lakers. On July 19, 2013, Madsen was promoted to a player development coach position with the Lakers.