Born on Frederiksberg in Copenhagen, Colding played his youth teamfootball for Ejby 68 and BK Frem. He made his Denmark under-21 national team debut on 25 August 1992. Colding first made himself noticed on the senior level, when he scored in Frem's 1–5 defeat to Real Zaragoza in the 1992–93 UEFA Cup tournament. When Frem went bankrupt in fall 1993, Colding moved to rivals Brøndby IF in the Danish Superliga championship. He debuted for the club in June 1994, and Colding made his debut for the Danish national team under national team coach Bo Johansson in November 1996. He was subsequently voted 1996 Brøndby IF Player of the Year. Following Brøndby's three Danish Superliga triumphs in a row from 1996 to 1998, and the club's qualification for the 1998–99 UEFA Champions League tournament, Colding became a mainstay in the Danish national team. He played in the majority of the Danish national team matches from 1998 to 2000, and he took part in all Denmark's matches at both the 1998 FIFA World Cup and UEFA Euro 2000. With the arrival of new national team coach Morten Olsen in June 2000, Colding's career for Denmark went on hiatus. With Brøndby, Colding won two Danish Cup trophies and three Danish football championships, and since March 1999 he captained the side when he took over the captain's armband from John Jensen. Colding moved abroad in winter 2000 to play for relegation battlers VfL Bochum in the German Bundesliga, in a transfer deal worth 1.5 million DEM. He debuted in January 2001 and played the last 16 games of the 2000–01 Bundesliga season, as Bochum ended dead last in the league and were relegated to the German 2. Bundesliga. The club won promotion the following year, with Colding the deputy team captain, a position he kept through his Bochum career as he captained the Bochum side in several games. The club finished in a meriting fifth place in the 2003–04 Bundesliga season, and Colding received his final call-up to the Danish national team, when Morten Olsen included him in the team that lost 0–2 to Spain in March 2004. Bochum were relegated again following the 2004–05 season, and Colding ended his career in the club following eight games played during the 2005–06 2. Bundesliga season, which once more ended in promotion for Bochum to the top-flight Bundesliga. Colding has been the general director for handball club AG København but left the club on 30 July 2012, just one day before the club filed for bankruptcy.
