Erste Amtszeit (2000–2001) und Wahl zum Parteivorsitzenden

Am 17. März 2000 wurde Stoltenberg während der laufenden Legislaturperiode neuer Ministerpräsident (Statsminister) und damit im Alter von 41 Jahren der bis dahin jüngste Inhaber dieses Amtes in der norwegischen Geschichte. Zuvor hatte Ministerpräsident Kjell Magne Bondevik von der Kristelig Folkeparti (KrF) bei einer Vertrauensfrage keine Mehrheit erhalten. In seiner Amtszeit versuchte Stoltenberg vor allem, eine Verwaltungsreform durchzusetzen. Dies führte zu einer Reform von Krankenhäusern, Polizei und Verteidigung sowie einer Neuregelung der Mehrwertsteuer. Außerdem wurde in seiner Zeit eine Regelung eingeführt, dass die staatlichen Einnahmen aus dem norwegischen Ölgeschäft in den staatlichen Pensionsfonds fließen müssen. Die meisten dieser angegangenen Reformen kamen bei der Bevölkerung nicht gut an. Während seiner Amtszeit wurde Norwegen zu einem der größten Geberländer für die Global Alliance for Vaccines and Immunisation (GAVI). Im Jahr 2001 wurde er Mitglied im Board of Directors der Organisation.

Bei der Parlamentswahl 2001 kam es zu einer Wahlniederlage der Arbeiderpartiet. Die Partei erhielt bei der Wahl das bis dahin schlechteste Ergebnis seit Ende des Zweiten Weltkriegs. Stoltenberg und seine Regierung traten daraufhin zurück und der KrF-Politiker Kjell Magne Bondevik wurde am 19. Oktober 2001 erneut Ministerpräsident. Stoltenberg kehrte nach seiner Zeit als Regierungschef ins Storting zurück. Dort gehörte er die gesamte Legislaturperiode lang bis Herbst 2005 dem Außenausschuss an und er fungierte als Fraktionsvorsitzender.

Durch die Wahlniederlage im Jahr 2001 wurde der zwischen Thorbjørn Jagland und Stoltenberg bereits in seinen Anfängen vorhandene Führungsstreit in der Arbeiderpartiet weiter verstärkt. In einer Autobiografie aus dem Jahr 2016 schrieb Stoltenberg, dass er in der Folge an Treffen teilnahm, in denen besprochen wurde, wie man Jagland aus dem Amt des Parteivorsitzenden entfernen könnte. Im Vergleich zu Jagland wurde Stoltenberg als der bessere Rhetoriker angesehen und im November 2002 wurde er zum neuen Parteivorsitzenden gewählt. In den Monaten nach Stoltenbergs Wahl konnte sich die Arbeiderpartiet in den Wahlumfragen kaum verbessern.

Zweite Amtszeit (2005–2013)

Bei der Parlamentswahl 2005 war Stoltenberg der Spitzenkandidat seiner Partei. Im Jahr 2003 ging er eine Zusammenarbeit mit den Parteien Sosialistisk Venstreparti (SV) und Senterpartiet (Sp) ein. Dieses Parteienbündnis trat im Wahlkampf mit dem Ziel, eine Mehrheitsregierung zu bilden, mit einer gemeinsamen Plattform an. Bei der Wahl gelang es den drei Parteien, eine Mehrheit im Parlament zu erhalten. Gestützt auf eine Koalition der drei Parteien wurde Stoltenberg am 17. Oktober 2005 erneut Ministerpräsident in der Regierung Stoltenberg II. Stoltenberg wurde dabei der erste Ministerpräsident seiner Partei seit 1945, der eine Regierungskoalition einging. Bei der Wahl 2009 gelang es den Regierungsparteien, die Mehrheit im Parlament zu behalten und Stoltenberg setzte seine Amtszeit als Ministerpräsident fort.

Im Jahr 2010 verhandelte er mit dem damaligen russischen Präsidenten Dmitri Medwedew über eine seit 40 Jahren umstrittene Grenze in der Barentssee. Sie konnten sich dabei auf einen Grenzverlauf einigen, bei dem beide Parteien einen ungefähr gleich großen Anteil am Gebiet, in dem sich Öl- und Gasvorkommen befinden, erhielten.

In Stoltenbergs zweite Regierungszeit fielen die Anschläge in Norwegen 2011. Während diesen Anschlägen wurden auf der Insel Utøya, die die Arbeiderpartiet für Ausflüge ihrer Parteijugend AUF nutzt, auch persönliche Bekannte Stoltenbergs ermordet. In seiner Rede nach dem Anschlag sagte er, dass die Antwort auf die Gewalt noch mehr Demokratie und noch mehr Offenheit sein solle, aber nie Naivität. Für seine Reaktion und Reden nach den Anschlägen erhielt er viel Rückhalt in der Bevölkerung. Eine Untersuchungskommission des Parlaments kritisierte jedoch im Anschluss, dass es den Behörden nicht gelang, die Bevölkerung vor einem Terroranschlag zu beschützen. Stoltenberg übernahm die Verantwortung für die Fehler dieser Zeit, er schloss jedoch einen Rücktritt aus. Er gab an, die Situation aus dem Amt heraus verbessern zu wollen.

Während seiner Amtszeit stiegen die Verteidigungsausgaben Norwegens an. Im Gegensatz zu seinem Koalitionspartner Senterpartiet war er Befürworter der norwegischen Mitgliedschaft im Europäischen Wirtschaftsraum (EWR) und er lehnte eine von seinem Koalitionspartner geforderte Neuverhandlung des Vertrags ab.

Bis 2012 wurde Stoltenberg in Umfragen häufig zum beliebtesten Politiker des Landes gewählt. Zur Stortingswahl 2013 hin sanken die Zustimmungswerte der Regierung jedoch. Bei der Wahl erhielt die Partei schließlich ihr bis dahin zweitschlechtestes Ergebnis seit 1924. Die Regierung Stoltenberg II trat im Anschluss an die Wahl zurück und wurde von der bürgerlichen Regierung Solberg abgelöst. Stoltenberg, der sein Mandat im Storting ab 2005 hatte ruhen lassen müssen, kehrte daraufhin als Abgeordneter in das Parlament zurück. Dort wurde er Fraktionsvorsitzender der Arbeiderpartiet-Fraktion.