Newcastle United

Caldwell begann seine Karriere in der Jugendabteilung des Premier-League-Vertreters Newcastle United. Im Sommer 1998 unterzeichnete er bei den Magpies seinen ersten Profivertrag. Sein Ligadebüt für den Verein gab er am 30. September 2000 im Spiel gegen Manchester United. Im weiteren Verlauf der Saison kam er auf insgesamt 10 Einsätze (davon 4 als Einwechselspieler). Sein erstes und einziges Ligator für Newcastle erzielte er ebenfalls in seiner ersten Profisaison, beim 4:3-League-Cup-Erfolg über seinen späteren Arbeitgeber Bradford City im November 2000. In den nächsten Jahren folgte eine Reihe an Leihgeschäften, um dem jungen Schotten weiter Spielpraxis zu gewähren. Im Oktober 2001 einigte man sich mit dem damaligen Drittligisten FC Blackpool über eine auf einen Monat beschränkte Kurzleihe. Nach seiner Rückkehr zu den Magpies wurde er im Dezember gleichen Jahres für einen Monat vom Zweitligisten Bradford City ausgeliehen, da dieser sich aufgrund von akuten Verletzungsproblemen vor personellen Engpässen im Defensivbereich wappnen wollte. Im neuen Jahr wurde der Vertrag in Bradford um einen weiteren Monat verlängert.

Nach seiner Rückkehr nach Newcastle kam er in der Saison 2002/03 auf insgesamt 17 Einsätze. Dazu gehörten sogar zwei Champions-League-Partien gegen Inter Mailand und Bayer 04 Leverkusen. Im Januar 2004 wurde er an den akut abstiegsbedrohten Ligakonkurrenten Leeds United verliehen, wo er jedoch den Abstieg in die Zweitklassigkeit nicht verhindern konnte.

AFC Sunderland

Nach seiner Rückkehr zu den Magpies wurde er im Sommer 2004 freigestellt, woraufhin ihn der damals zweitklassige AFC Sunderland verpflichtete. Dort formierte er mit seinem Innenverteidigerkollegen Gary Breen eine solide Abwehrreihe, durch die die Black Cats in der Saison 2004/05 die Football League Championship gewannen und somit in die Premier League zurückkehrten. In der darauffolgenden Saison zog er sich bereits zu Beginn der Spielzeit eine schwere Knieverletzung zu, die ihn für lange Zeit außer Gefecht setzte. Nachdem er sich vollständig erholt hatte, hatte er jedoch seinen Stammplatz im Team nicht mehr sicher und wurde im Laufe der Zeit immer seltener eingesetzt. Zudem folge nach einer Spielzeit in der höchsten Spielklasse bereits der direkte Wiederabstieg.

FC Burnley

Aus diesem Grund bat er im Winter 2007 die Vereinsführung, den Klub verlassen zu dürfen, sodass sich der Zweitligist FC Burnley seine Dienste mit einem Dreijahresvertrag sichern konnte. In der Mannschaft wurde er zum Kapitän ernannt und absolvierte in den folgenden drei Jahren über 100 Spiele für den Klub. In der Saison 2008/09 schaffte er mit der Mannschaft den Aufstieg in die Premier League. Da in der folgenden Saison jedoch der direkte Wiederabstieg folgte und personelle Sparmaßnahmen nötig waren, wurde sein auslaufender Vertrag wurde verlängert.

Wigan Athletic

Nachdem er sich zwischenzeitlich bei den Bolton Wanderers fit gehalten hatte und Angebote von Preston North End und dem FC Portsmouth abgelehnt hatte, verpflichtete ihn schließlich Wigan Athletic im August 2010 für ein Jahr. Dort spielte er nun, wie bereits in den ersten Jahren in Newcastle, mit seinem Bruder Gary zusammen. Sein Debüt für seinen neuen Verein gab er in der zweiten Runde des League Cups beim 3:0-Erfolg über Hartlepool United. Im Laufe der Saison konnte sich Caldwell jedoch nicht durchsetzen und kam nur auf 10 Ligaeinsätze für die Latics, sodass sein auslaufender Vertrag im Juni 2011 nicht verlängert wurde.

Birmingham City

Deshalb einigte er sich im Juli 2011 mit dem Premier-League-Absteiger Birmingham City auf einen Einjahresvertrag. Sein Debüt für den Verein gab er am 6. August 2011, bei der 1:2-Heimniederlage gegen Derby County. Im Laufe der Saison festigte Caldwell seinen Stammplatz bei den Blues.