Krøldrup påbörjade sin karriär i Aalborg Chang och gick senare vidare till B 93. 2001 tog han steget ut till Italien och Udinese i Serie A. I Udinese spelade han tillsammans med landsmannen Martin Jørgensen som i mars 2002 sade att han tyckte att Krøldrup var redo för landslaget. I februari 2004 togs han för första gången med i truppen till en match mot Turkiet. Han var även del av truppen i EM 2004 men fick inte spela några matcher.
Efter fyra framgångsrika år i Italien flyttade han till engelskaEverton – en övergång värd fem miljoner brittiska pund.[1] Evertons tränare David Moyes berömde Krøldrup med orden "ung, entusiastisk och ivrig att förbättras", men han nämnde också att han är något av ett risktagande för att han är okänd i Premier League.[1] Övergången skedde i sena juni 2005 men en skada under försäsongsträningen hindrade Krøldrup från att göra sin debut för Everton. Han tillbringade mycket tid på avbytarbänken tills han i januari 2006 återvände till Italien och denna gång Fiorentina, efter att ha spelat bara två matcher för Everton.
18 juli2007 utsågs Krøldrup av TimesOnline till att ha varit den sämsta övergången i Premier League.[2]