Colding debuterede for Brøndby i juni 1994, og han fik sin debut for det danske A-landshold under landstræner [[Bo Johansson]] i november 1996. Han blev efterfølgende kåret til årets spiller i Brøndby 1996. Efter Brøndbys tre danske Superligatriumfer i træk fra 1996 til 1998 og klubbens kvalifikation til [[UEFA Champions League 1998-99]] blev Colding stamspiller på det danske landshold. Han spillede i størstedelen af det danske landsholds kampe 1998-2000, og han deltog i alle Danmarks kampe ved både VM i 1998 og EM 2000. Da [[Morten Olsen]] i juni 2000 tiltrådte som landstræner, blev Coldings landsholdskarriere sat på pause. Med Brøndby vandt Colding to [[DBU Pokalen|danske pokaltitler]] og tre [[Danmarksmesterskab (fodbold)|danske mesterskaber]], og fra marts 1999 var han anfører for holdet, efter han overtog armbindet fra [[John "Faxe" Jensen|John Jensen]].
Levende_personer