Fußballerische Anfänge

Nordtveit begann seine Karriere in der Jugend seines Heimatvereins SK Vats. Später wechselte er für kurze Zeit zum etwas größeren Skjold IL. Dort wurde er bei einem Jugendturnier vom FK Haugesund entdeckt und unter Vertrag genommen. Nach nur einem Jahr in der Jugend debütierte der als talentiert geltende 16-Jährige für Haugesund in der Adeccoligaen. Gleichzeitig erfolgte die Berufung in die norwegische U16-Nationalmannschaft, deren Kapitän er bald wurde. Innerhalb kürzester Zeit erarbeitete er sich den Ruf, eines der größten Abwehrtalente in Europa zu sein, der eine Vielzahl internationaler Scouts ins Haugesund-Stadion führte.

Wechsel zu Arsenal und verschiedene Leihgeschäfte

Zunächst deutete alles auf einen Wechsel zu Manchester United hin. Nach nur drei Ligaspielen bekam Nordtveit ein Vertragsangebot, das Haugesund allerdings ablehnte. Im Juni 2007 beobachtete der Coach vom FC Arsenal, Arsène Wenger, den Spieler persönlich. Arsenal einigte sich mit Haugesund auf eine Ablösesumme von ca. 1,8 Mio. Euro, die unter einer bestimmten Anzahl von Einsätzen auf ca. 3 Mio. Euro steigen konnte.

Bei Arsenal kam Nordtveit gleich nach seinem Wechsel im Testspiel gegen den FC Barnet zum Einsatz. In der Folge führte er die Reserve-Mannschaft von Arsenal als Kapitän in die Saison. Nach guten konstanten Leistungen über die Saison hinweg wurde er im letzten Spiel der Saison 2007/08 gegen den FC Sunderland in den Profikader nominiert, kam jedoch nicht zum Einsatz.

Im Zuge der Kooperation von Arsenal mit dem spanischen Zweitligisten UD Salamanca wurde Nordtveit für die Saison 2008/09 für ein halbes Jahr ausgeliehen. Wenger holte den Spieler allerdings schon nach drei Monaten wieder zurück, da er zu wenig Spielzeit bekam. Nach einem kurzen Gastspiel beim norwegischen Lillestrøm SK von März bis Juli 2009 wurde er auf Wunsch von Wenger zum deutschen Klub 1. FC Nürnberg, der zuvor in die Fußball-Bundesliga aufstieg, weiterverliehen.

Dort kam er am dritten Spieltag der Saison 2009/10 zu seinem ersten Einsatz, als er zu Beginn der zweiten Halbzeit für den verletzten Andreas Wolf eingewechselt wurde. Das Heimspiel endete 0:2 gegen Hannover 96. Danach spielte er fast durchgängig in der Hinrunde, die für den Club auf einem Abstiegsplatz endete. Deshalb wurde in der Winterpause Breno für die Innenverteidigung ausgeliehen, und Nordtveit verlor seinen Stammplatz. Erst nach einer Verletzung des Brasilianers kehrte er in die Startaufstellung zurück, kam aber insgesamt nur noch dreimal über die vollen 90 Minuten zum Einsatz und wurde auch in den beiden Relegationsspielen nicht eingesetzt.

Borussia Mönchengladbach

Zur Winterpause 2010/11 wechselte Nordtveit endgültig zurück in die deutsche Bundesliga zu Borussia Mönchengladbach. Von Beginn an stand er in der Stammelf seiner neuen Mannschaft. Anfangs als Innen- oder Rechtsverteidiger eingesetzt, bildete er bald mit Roman Neustädter ein gut eingespieltes Tandem im defensiven Mittelfeld. Sein erstes Tor für die Gladbacher erzielte Nordtveit am 10. April 2011 am 29. Spieltag im Rheinischen Derby gegen den 1. FC Köln mit dem Treffer zum 5:1-Endstand. Er kam in der Saison 2011/12 und seiner ersten kompletten Saison für Gladbach, in der der Klub nahezu die gesamte Saison die Plätze für den Europapokal bzw. für die Europapokal-Qualifikation besetzte, zu 31 Einsätzen, in denen er ein Tor erzielte. Zum Saisonende belegte die Borussia den vierten Tabellenplatz, wodurch sie sich für die Play-offs zur UEFA Champions League qualifizierten. Nordtveit reifte in Mönchengladbach zum Führungsspieler und wurde einige Male als Mannschaftskapitän eingesetzt. In der Saison 2015/16 spielte er wettbewerbsübergreifend 39 Spiele für Borussia Mönchengladbach und erzielte vier Tore. Er wurde in der Defensive auf verschiedenen Positionen eingesetzt, meistens aber als Innenverteidiger in einer Dreierkette. Am Ende der Saison erreichte Borussia Mönchengladbach mit dem vierten Tabellenplatz die Play-offs der UEFA Champions League.

West Ham United

Nach fünfeinhalb Jahren in Mönchengladbach verließ Nordtveit nach Ablauf seines Vertrages im Sommer 2016 den Verein in Richtung England. Er unterschrieb einen Vertrag über eine Laufzeit von fünf Jahren bei West Ham United.

TSG 1899 Hoffenheim und Leihe nach Fulham

Zur Saison 2017/18 wechselte Nordtveit zum Bundesligisten TSG 1899 Hoffenheim und unterschrieb einen bis 2022 laufenden Vertrag. Im Januar 2019 wurde er bis zum Saisonende an den englischen Erstligisten FC Fulham verliehen; mit dem Aufsteiger stieg er direkt wieder aus der Premier League ab und kehrte anschließend zu Hoffenheim zurück. Seinen Vertrag wird er im Sommer 2022 nicht verlängern.