Jens Stoltenberg

Bakgrunn og yrkeskarrière

På farssiden tilhører han Stoltenberg-slekten fra Vestfold. På morssiden nedstammer Stoltenberg fra embetsmannsslekten Heiberg. Oldefaren Eivind Heiberg var direktør for Norsk Arbeidsgiverforening 1912–1917.
Stoltenberg vokste opp i en politisk engasjert familie. Hans far, Thorvald Stoltenberg, har hatt en rekke viktige posisjoner for Arbeiderpartiet, blant annet som forsvarsminister 1979–1981 og utenriksminister 1987–1989 og 1990–1993. Moren var tidligere statssekretær Karin Stoltenberg, søster av Marianne Heiberg (som var gift med avdøde forsvars-/utenriksminister Johan Jørgen Holst). Stoltenberg har søsteren Camilla, og hadde også søsteren Nini, som døde i 2014. Han er gift med Ingrid Schulerud, og de har to barn. Faren Thorvald hadde med familien da han var ved ambassaden i Beograd da Jens Stoltenberg var liten og som liten lærte han både engelsk og serbokroatisk.
Stoltenberg gikk grunnskole ved Rudolf Steinerskolen i Oslo og i Bærum, og videregående skole ved Oslo katedralskole i 1978. Han slet med både lesing og matematikk i grunnskolen, men har uttrykt at han likevel ikke opplevde skolegangen som spesielt vanskelig. I årene 1979–1980 avtjente han førstegangstjenesten, først ved Infanteriets øvingsavdeling på Evjemoen i Aust-Agder. Resten av tjenesten tilbrakte han som journalist i Soldatnytt, et magasin for vernepliktige soldater, utgitt av Tillitsvalgtsordningen i Forsvaret. Deretter studerte han sosialøkonomi ved Universitetet i Oslo hvor den såkalte «Osloskolen» – en variant av Keynes' teorier – stod sterkt. Stoltenberg har omtalt seg selv som keynesianer. Han ble i 1987 uteksaminert som cand.oecon. med god karakter (2,28). Hovedoppgaven Makroøkonomisk planlegging under usikkerhet handlet om strategier for optimal utvinning og bruk av inntekter fra oljeutvinning. Oppgaven ble utgitt som internt notat i forbindelse med Statistisk sentralbyrå sitt oljeøkonomiprosjekt i 1985, ti år etter Oljemeldingen.
Stoltenberg jobbet som deltidsjournalist i Arbeiderbladet 1979–1981, som konsulent i Statistisk sentralbyrå 1989–1990 og som timelærer i samfunnsøkonomi ved Universitetet i Oslo 1989–1990. I Statistisk sentralbyrå arbeidet Stoltenberg blant annet med å teste og anvende det sentrale modellverktøyet for makroøkonomiske kort- og langtidsberegninger – MODAG og MSG.

AUF-tiden

Stoltenberg har vært medlem av Arbeiderpartiet siden han var 14 år.
I 1973 begynte han – sammen med noen klassekamerater fra Steinerskolen – å gå på møter i AUF-laget Centrum AUL, og etter kort tid tok den samme gjengen ansvar for å reetablere AUF-laget på Majorstua med Stoltenberg som formann. Han var et naturlig midtpunkt og en ivrig medlemsverver. Majorstu-laget ble snart et tyngdepunkt i Oslo AUF til tross for at lagets medlemsmasse var preget av ressurssterk, intellektuell ungdom som kulturelt stod nokså fjernt fra den tradisjonelle arbeiderbevegelsen.
I 1978 ble Stoltenberg medlem i sentralstyret i Norges Gymnasiastsamband (NGS), som en av de første AUF-erne siden 1960-tallet.
Han var sentralstyremedlem i Arbeidernes ungdomsfylking (AUF) fra 1979, nestleder fra 1983 og ungdomspartiets leder fra 1985 til 1989. I denne perioden var han også visepresident i Den sosialistiske ungdomsinternasjonale (International Union of Socialist Youth, IUSY). Han knyttet et bredt politisk nettverk, ikke minst til svenske sosialdemokratiske ungdomsledere, som Anna Lindh og Mona Sahlin. 
Stoltenbergs ledertid i AUF var preget av større harmoni og ro i forholdet til moderpartiet enn før, av mer moderate politiske holdninger og av organisatoriske endringer.
Hans politiske retning hadde kommet fram allerede på AUF-landsmøtet i 1981, mens Stoltenberg ennå bare var sentralstyremedlem, men i tillegg medlem av redaksjonskomiteen for et nytt prinsipprogram. Det forelå på forhånd et utkast, som Thorbjørn Jagland i sitt siste år som AUF-leder var hovedansvarlig for. Redaksjonskomiteen ønsket å fjerne blant annet en setning om at «lønnsarbeiderklassen står i en uløselig interessemotsetning til kapitalismen» og endre målet om «sosialistisk planøkonomi» til «sosialistisk økonomi». På begge disse punktene tapte redaksjonskomiteen og Stoltenberg voteringene.
I sin egen lederperiode i ungdomsfylkingen, fra 1985 av, fikk så Stoltenberg større gjennomslag for en politikk som ikke lenger var på kollisjonskurs med moderpartiet i samme grad som AUF tidligere hadde hatt tradisjon for. AUF hadde fattet sitt første vedtak mot norsk medlemskap i NATO i 1969, og standpunktet hadde blitt stadfestet på hvert landsmøte siden, helt frem til landsmøtet i 1987. Stoltenberg og et enstemmig sentralstyre mente da at en mer hensiktsmessig politikk ville være «nærkamp» internt i NATO for et blokkfritt og atomvåpenfritt Europa. Forslaget ble vedtatt på landsmøtet med 169 mot 125 stemmer.
En annen symbolsak som kom opp på det samme landsmøtet, var spørsmålet om karakterer i videregående skole. Tradisjonelt var AUF mot, men også her ønsket Stoltenberg en revisjon. Han mente at så lenge alternativet til karakterer var opptaksprøver ved opptak til høyere utdanning, så var karakterer det minste ondet. Her fikk lederen landsmøtet mot seg – 159 stemte mot karakterer, 126 for. 
Stoltenberg tok også til orde for organisasjonsmessige endringer i AUF og lanserte i 1987 en offensiv under slagordet «Nye AUF».
Hovedgrepene i denne satsingen var for det første å sørge for at lokal- og fylkeslagene drev sin virksomhet mer målrettet etter en sentralt vedtatt plan, for det andre å sikte seg inn mot nye grupper ungdom (av de som ble nevnt, var kristne, motorinteresserte, rockegjenger, innvandrere og idrettsfolk), for det tredje å fornye bildet av organisasjonen, inkludert valg av symboler, sanger og andre kulturuttrykk. Alt dette skulle samordnes i en offensiv med medlemsverving og lagsbygging. En dobling av antall lag (fra 500 til 1000) fram til år 2000 ble nevnt som et mål. Organisasjonsplanen vakte noe motstand på landsmøtet, men hovedtrekkene ble vedtatt.
Stoltenberg var leder for Mannsrolleutvalget fra 1986 til 1987 og medlem videre frem til 1990.

Medlemsjukset i AUF

I siste halvdel av 1990-tallet ble det kjent at en rekke ungdomsorganisasjoner hadde operert med for høye medlemstall, og at de slik hadde mottatt for mye offentlig støtte. Den første avsløringen kom i VG 2. mars 1995 og gjaldt Oslo AUF. Saken rullet videre og omfattet til sist 24 ungdomsorganisasjoner, som ble anmeldt for bedrageri i en eller annen form av Samferdselsdepartementet.
For AUF lød tiltalen på mildeste form. Dette ble kritisert som en vennetjeneste overfor regjeringskollega Stoltenberg. Simpelt bedrageri har nemlig en foreldelsesfrist på bare fem år, slik at Stoltenbergs ledertid falt utenfor etterforskningen. Samferdselsminister Opseth avviste dette. Etter klager ble forøvrig tiltalen mot AUF og de fleste andre organisasjonene frafalt på grunn av bevisets stilling. 
I januar 1998 kom medlemsjukset likevel opp for retten, da det ble reist tiltale mot fire enkeltstående tillitsvalgte i Oslo AUF. Stoltenberg var innkalt som vitne. Han vedgikk å kjenne til en praksis som ble kalt forskuttering,
men avviste at han visste noe om fiktive innbetalinger eller annen triksing. De fire tiltalte ble alle dømt for bedrageri.

1990-tallet

Fra 1990 fikk Stoltenberg stadig tyngre verv i moderpartiet – først fram til 1992 som leder i Oslo Arbeiderparti, og fra dette året som nestleder i landspartiet. Han var statssekretær i Miljøverndepartementet 1990–1991 under Thorbjørn Berntsen. Fra denne posisjonen ledet han Arbeiderpartiets miljøutvalg. 
Stoltenberg ble ved stortingsvalget 1989 tredje vararepresentant til Stortinget fra Arbeiderpartiet i Oslo. Han møtte fast for Bjørn Tore Godal 1991–1993. I 1993 ble han valgt inn på eget mandat og har siden blitt gjenvalgt, men har vært erstattet av vararepresentanter i regjeringsperiodene 1993–1997, 2000–2001, 2005-2013 og fra 2014. Han var leder i Stortingets energi- og miljøkomité fra 1997 frem til han ble statsminister i 2000. 
Stoltenberg har også hatt interesse for energipolitikk og var nærings- og energiminister under Gro Harlem Brundtland 1993–1996. Han var en periode nestleder i Forum for verdiskaping. På denne tiden deltok han også i diskusjonene om energi- og oljepolitiske saker i en uformell «oljegruppe», som Finn Kristensen hadde opprettet på siden av partiorganene, og gruppens medlemmer fikk i ettertid intern kritikk for det. I Thorbjørn Jaglands regjering var han finansminister fra tiltredelsen i 1996 til dens avgang etter valget i 1997. I tillegg til statsministerposten har Stoltenberg altså vært tilknyttet eller ledet departementene for miljø, næring, energi og finanspolitikk. 
Han var medlem av Forsvarskommisjonen av 1990 frem til 1992.

Maktkampen mot Thorbjørn Jagland

Under Arbeiderpartiets landsmøte i november 1992 ga Gro Harlem Brundtland overraskende beskjed om at hun ønsket å gå av som partileder. Valgkomiteen under ledelse av LO-leder Yngve Hågensen fikk dermed et uventet komplisert oppdrag. Nestleder Gunnar Berge ble ansett som en naturlig etterfølger i toppvervet, men ønsket selv ikke å stille. Stoltenberg og Thorbjørn Jagland ble dermed de mest sentrale lederkandidatene. Mens Oslo Arbeiderparti og AUF støttet Stoltenberg, hadde Jagland mektige støttespillere spesielt i LO. Det så lenge ut til å gå mot en kampvotering mellom de to kronprinsene, men Stoltenberg trakk sitt kandidatur – «av familiære grunner» – kort tid før landsmøtet skulle votere. Dermed endte maktkampen med at Jagland tok over ledervervet. I etterkant kom det frem at Hågensen hadde vurdert at Stoltenberg langt fra var moden nok til et så tungt verv.
Jagland gikk av som statsminister etter valget i 1997 etter å ha satt en minimumsgrense på 36,9 % av stemmene for å fortsette. Valgnederlaget fikk deler av partiet til å ønske omkamp om ledervervet, men ett år etter valget lå Ap på sterke 40 % på meningsmålingene. Jaglands posisjon i partiet var derfor i liten grad truet. Samtidig hadde Stoltenberg mistet mange av sine viktigste støttespillere, og navn som Hill-Marta Solberg og Trond Giske ble stadig oftere nevnt som partiets neste ledere.
Med 28,2 % gjorde Arbeiderpartiet et elendig kommunestyre- og fylkestingsvalg i 1999. Dette førte til at lederdebatten blusset opp igjen innad i partiet. I januar 2000 gikk Oslo Arbeiderparti og flere fylkeledere inn for å kaste Jagland som partileder til fordel for Stoltenberg. Etter flere uker med store spekulasjoner i media og et enormt press valgte Jagland å trekke seg som parlamentarisk leder og statsministerkandidat i februar. Jagland beholdt det formelle vervet som partileder, men nå ble Stoltenberg partiets frontfigur - som statsministerkandidat og leder for stortingsgruppen.

Tiden som nærings- og energiminister

Stoltenberg fikk sin første statsrådspost høsten 1993, da han overtok ledelsen av det relativt nyetablerte Nærings- og energidepartementet i Gro Harlem Brundtlands tredje regjering. 
Han fikk straks store oppgaver med å avklare Norges forhold til EU når det gjaldt oljepolitikken. Unionen var i ferd med å utvikle et oljedirektiv, og det var forhandlinger om hvordan dette – med grunnlag i EØS-avtalen – skulle implementeres i Norge, som var områdets eneste store oljeproduserende land med de særlige interesser dette medførte. Stoltenberg og regjeringen valgte å ikke kreve unntak fra oljedirektivet. I stedet ble regjeringen enig med EU om et spesielt tillegg til den norske tiltredelseserklæringen til Maastricht-traktaten. Stoltenberg mente at dette ville være en tryggere og mer varig løsning enn unntak fra et direktiv som senere kunne endres. I Stortinget argumenterte han kraftig for regjeringens løsning.
Dette var en av flere saker der Stoltenberg var et viktig kort i regjeringens arbeid for norsk EU-medlemskap. Da det imidlertid ble nei-flertall ved folkeavstemningen i 1994, falt løsningen med et tillegg til tiltredelseserklæringen bort, og det måtte foretas nye forhandlingsrunder om oljedirektivet. En annen sentral EU-tilpasningssak i denne perioden var endringer i konsesjonsloven, ettersom EØS-avtalen ikke tillot forskjellsbehandling av norske og utenlandske eiere. Fra 1996 skjedde også en endring i norsk alkoholpolitikk, da Vinmonopolets produksjons- og importdel ble skilt ut i firmaet Arcus, som ble lagt inn under Næringsdepartementet. I og med dette ble det også åpnet for privat import av alkohol.
I 1994 kom Stoltenberg med en stortingsmelding om olje- og gasspolitikken. Her ble det åpnet for leteboring i Skagerrak og utenfor Nordland, noe som provoserte miljøbevegelsen.
Meldingen inneholdt også et forslag om nye regler for leting i Barentshavet. Stoltenberg argumenterte i denne sammenheng med at det ville være riktig å hente ut oljen mens vi visste hva den var verdt. Den ville være til liten glede for fremtidige generasjoner om den ble liggende til den «blir like verdiløs som kullet». 
Seinere i perioden gikk Stoltenberg også inn for bygging av gasskraftverk i Norge, noe han hadde vært mot da han var statssekretær i Miljøverndepartementet i 1990. Det nye standpunktet ble begrunnet med at man burde se Norden som et felles energiområde, og at et norsk gasskraftverk ville kunne erstatte finske og danske kullkraftverk og svenske atomkraftverk. I 1990 hadde målet vært å stabilisere norske CO2-utslipp på 1989-nivå innen 2000.
I mai 1997, da Stoltenberg var finansminister, kom det frem at han i 1995 hadde bedt Stiftelsen for samfunns- og næringslivsforskning fjerne to kapitler i en rapport om gasskraft. Ifølge Stoltenberg skjedde dette fordi det ikke var snakk om forskning, men utredning, og fordi «problemstillingene som var tatt opp av SNF, lå utenfor oppdraget». 
Av mye omtalte industrisaker i Stoltenbergs statsrådstid var nedleggingen av Sydvaranger og Rena kartonfabrikk og innskrenkinger ved Freia, som var blitt solgt til Kraft Foods. På oljesiden åpnet Trollfeltet sin produksjon den 19. juni 1996.
En del utenlandsbesøk i perioden førte til diskusjon. I 1995 og 1996 var Stoltenberg i Aserbajdsjan. Han inngikk her en samarbeidsavtale, og kom med uttalelser om finansiering av norsk velferd ved oljeutvinning i utlandet.
Også et besøk i Indonesia like etter diverse menneskerettsbrudd, og kort tid etter at fredsprisutdelingen til Carlos Filipe Ximenes Belo og José Ramos-Horta hadde satt søkelys på landets okkupasjon av Øst-Timor, førte til kritikk.

Tiden som finansminister

Stoltenberg forlot Nærings- og energidepartementet i oktober 1996. Han ble da finansminister i Thorbjørn Jaglands regjering, som ble sittende frem til etter stortingsvalget 1997. Den korte tiden ga ham ikke anledning til å vise sin politikk i et statsbudsjett som var fullt og helt hans eget. Budsjettet for 1997 var i all hovedsak produsert under ledelse av avtroppende finansminister Sigbjørn Johnsen, mens budsjettet for 1998 naturlig nok ble endret av den påtroppende regjeringen Bondevik.
Et hovedanliggende for Stoltenberg i perioden var å sikre en stabil kronekurs gjennom et stramt statsbudsjett.
På Arbeiderpartiets landsmøte i november 2006 spissformulerte han det slik: «Hvem som helst kan bruke penger. Det er verdens enkleste sak. Det er ikke alltid lett å la være å bruke penger. Det er det vi skal gjøre nå.»
Dette viste seg imidlertid vanskelig, og verdien av kronen varierte sterkt gjennom året. I juli 1997 valgte Norges Bank – med regjeringens samtykke – å heve dagslånsrenten for første gang på fem år.
Et spørsmål som kom opp, var om Norges Bank burde ha en mer uavhengig stilling, noe Stoltenberg avviste.
Det ble også vurdert om kronen skulle knyttes fast opp mot den nye europeiske valutaen euro. 
En konkret sak som vakte debatt, var avgjørelsen om å fravike gevinstbeskatning ved fusjonen mellom Aker og RGI, som særlig ville kunne være gunstig for Kjell Inge Røkke.
Stoltenberg måtte ellers i sitt år som finansminister ta stilling til flere saker som angikk norsk bankstruktur. Den største saken gjaldt fusjon mellom Kreditkassen (med staten som største aksjonær) og Storebrand. Fusjonsplanen var støttet av Stoltenberg, men ble avvist av Kjell Inge Røkke og Jens P. Heyerdahl (Orkla), som hadde store aksjeposter i Storebrand. Fusjonen ble dermed ikke noe av.
En forventet fusjon mellom Postbanken og Kommunalbanken ble det heller ikke noe av. 
I forholdet til EU var en sentral sak et vedtak i ESA om at den differensierte arbeidsgiveravgiften i Norge delvis var i strid med EØS-avtalen, noe Stoltenberg var uenig i.
Saken endte med at ordningen bortfalt, men at Norge fikk beholde en kompensasjonsordning for kommunene som mistet differensiert arbeidsgiveravgift, og som fortsatt (2011) forvaltes over Kommunal- og regionaldepartementets budsjett.
I hans senere statsministertid skulle en av Stoltenbergs viktige saker bli store endringer i pensjonssystemet. Men også i finansministerperioden skjedde det endringer, da ordningen med pensjonssparing med skattefradrag ble utvidet.
Stoltenberg mente imidlertid at det ikke skulle være behov for endringer i folketrygdens regler før 2050.
Et element i sikringen av folketrygden var beslutningen om å åpne for å plassere Oljefondets midler i utenlandske aksjer.

Periodene som statsminister

Stoltenbergs inntreden som parlamentarisk leder og statsministerkandidat førte til økende oppslutning på meningsmålinger. Fra 1999 ble det klart at Bondevik I-regjeringen slet med indre samarbeidsproblemer. Vel én måned etter Stoltenbergs tiltredelse som parlamentarisk leder, falt Bondeviks sentrumsregjering på et kabinettsspørsmål om utbygging av gasskraftverk, og Arbeiderpartiet overtok regjeringsmakten med et klart mindretall i Stortinget bak seg.

Jens Stoltenbergs første regjering

Stoltenberg og hans første regjering tiltrådte 17. mars 2000, etter at Bondevik I-regjeringen hadde gått av på grunn av et nederlag i Stortinget på et kabinettsspørsmål om energipolitikken. Den nye regjeringen var en ren Arbeiderparti-regjering. Den ble sittende til 19. oktober 2001, da den gikk av på grunn av svakt resultat ved stortingsvalget samme høst.
I regjeringen tok Stoltenberg blant annet med den forrige partilederen, Thorbjørn Jagland, som utenriksminister, og Trond Giske kom med som utdanningsminister. I tillegg til Giske hadde flere av statssekretærene tilhørt nei-fløyen i EU-striden i 1994.
I regjeringserklæringen het det at en ønsket en mer aktiv Europa-politikk og større satsing på miljø og internasjonal solidaritet. Regjeringen ville bidra til økt e-handel og bruk av informasjonsteknologi, og den ville arbeide for at mer av Norges kraftbehov kunne dekkes ved å produsere strøm av norsk gass. Det ble også varslet delprivatisering av Telenor.
Stoltenberg-regjeringen ville også ha økt innsats for «modernisering» og «effektivisering» av offentlig sektor, i tråd med utredningsarbeid som var blitt gjennomført i lang tid om spørsmålet. Allerede i 1989 hadde Hermansen-utvalget tatt opp eldre forslag om en bedre organisering av offentlig sektor, gjennom utredningen Om en bedre organisert stat. På årsmøtet i Østfold Arbeiderparti i mars 2000 advarte statsministeren mot å gjøre privatisering til et spørsmål om ideologi. Sykehussektoren var noe av det første som ville bli analysert. 
Signalene vakte bekymring og uro i partiorganisasjonen og fagbevegelsen. I Oslo var hovedparolen 1. mai 2000 «Forsvar velferdsstaten – kamp mot nedbygging og privatisering», noe som ble ansett som en klar advarsel til Stoltenberg. En annen parole gikk mot privatisering av Statoil og SDØE, en sak som for øvrig hadde vakt sterkt engasjement blant veteraner i Arbeiderpartiet. Haakon Lie, Tor Aspengren, Jens Christian Hauge og Finn Lied uttrykte i et brev til partiets sentralstyre kraftig motstand mot å fravike statens eiendomsrett til naturressursene. I en meningsmåling var 53 prosent av Ap-velgerne mot delprivatisering av Statoil og Telenor, mens 34 prosent var for. 
Stoltenberg og regjeringen ønsket likevel – med støtte i et landsstyrevedtak i februar – å delprivatisere Statoil raskt. Partimotstanden var imidlertid stor; blant annet var det eksplisitte vedtak mot delprivatisering i seks fylker og krav om landsmøtebehandling i ytterligere fire. På et sentralstyremøte i mai ble det derfor bestemt å utsette endelig vedtak til landsmøtet. Utover høsten tilspisset striden seg; noen nei-fylker gjentok sine vedtak, andre prøvde på kompromisser, mens kystfylkene på Vestlandet fattet vedtak for delprivatisering av Statoil og kommersialisering av SDØE. På landsmøtet i november ble det etter lange og strie forhandlinger seier for en modifisert versjon av Stoltenbergs linje. Stortinget vedtok så i april året etter å selge en tredjedel av Statoil og 21,5 prosent av SDØE.
En annen stor sak som regjeringen kjørte gjennom i stort tempo, var sykehusreformen. Tore Tønne var ansvarlig statsråd i Sosial- og helsedepartementet, og allerede i et foredrag i juni lanserte Stoltenberg planen om å overføre sykehusene fra fylkeskommunene til selvstendige økonomiske foretak. Samtidig advarte han mot en situasjon der partiet «mister grepet og ender opp som en konservativ bevegelse som forsvarer det bestående, og som utviklingen går forbi». På landsmøtet høsten 2000 fikk denne planen støtte, mens LO motsatte seg foretaksmodellen, men aksepterte statlig overtakelse av sykehusene. Norsk Kommuneforbund (nå Fagforbundet) var også svært negativ til et forslag om å privatisere de ikke-medisinske tjenestene (kjøkken, rengjøring m.v.). Den nye loven om helseforetak ble vedtatt i Stortinget sommeren 2001 med virkning fra 1. januar 2002.
I spørsmålet om norsk medlemskap i EU ønsket Stoltenberg og partileder Thorbjørn Jagland å ha mulighet til å sende en ny medlemskapssøknad. Landsmøtet ga åpning for dette i et kompromiss som sa at «en ny søknadsprosess kan startes opp i neste stortingsperiode med sikte på en søknad tidligst i 2005–2006», altså i løpet av den påfølgende stortingsperioden. 
Mindretallsregjeringen Stoltenberg fikk like store problemer i forholdet til Stortinget som den foregående mindretallsregjeringen til Bondevik, muligens større fordi Stoltenberg hadde mindre muligheter enn Kjell Magne Bondevik til å velge mellom støtte fra høyre- eller venstresiden. Regjeringen fikk likevel gjennomført noen betydelige, strukturelle reformer, som man ikke helt fikk se virkningene av mens regjeringen satt. Særlig gjaldt dette reformene innenfor sykehusene, politiet og forsvaret. En svært dramatisk, utenrikspolitisk sak oppstod like før valget da det norske lasteskipet MS «Tampa» tok opp 430 afghanske flyktninger utenfor australsk farvann den 26. august 2001. I denne spente saken var både utenriksminister Jagland og statsminister Stoltenberg direkte involvert, og det falt uvanlig sterk ordbruk og etterhvert australsk militær bording av skipet, 
inntil Australias statsminister John Howard i september fikk til en ordning hvor flyktningene kom i land på Nauru.
Stoltenbergs regjering måtte vike for Kjell Magne Bondeviks andre regjering da valgresultatet i 2001 viste klar borgerlig seier, og det dårligste resultatet for Arbeiderpartiet siden mellomkrigstiden. Arbeiderpartiet fikk bare 24,3 prosent oppslutning i valget. Stoltenberg gikk tilbake til Stortinget som parlamentarisk leder og medlem i Utenrikskomiteen, Valgkomiteen og Den utvidede utenrikskomiteen ut stortingsperioden. Særlig sykehusreformen hadde vakt intern strid i Arbeiderpartiet og fagbevegelsen før valget, og mange i partiet mente man hadde satset for mye på rasjonelle reformer og for lite på populær politikk som kunne vinne valg. For Stoltenberg ble problemene i mindretallsregjering en viktig inspirasjon for å starte arbeidet for stabile flertallsregjeringer sammen med andre partier.

Partileder

Stortingsvalget 2001 var et stort tap for Arbeiderpartiet, med et fall fra 35 til 24,3 prosent av stemmene, og skyldtes formodentlig at partiet overtok regjeringsmakten uten å ha noe særlig handlingsrom med hensyn til Stortinget. Valgresultatet ble partiets dårligste siden de indre stridighetene i 1920-årene og stortingsvalget 1924, og personkonflikten på øverste nivå tilspisset seg. I 2002 ble til slutt Jagland erstattet som partileder av Stoltenberg, uten at dette kom som noen overraskelse for mange i partiet. Det ble først sagt at striden skulle avgjøres ved partiets landsmøte i 2004, men i 2002 trakk Jagland seg fra vervet uten noen avstemning grunnet helseplager. Jagland hadde også følt et uttalt ansvar for å avslutte den destruktive personstriden.
Som partileder har Stoltenberg introdusert en rekke rådgivere på ulike felt som han selv har håndplukket. I hans første regjering var det slik at statsrådene selv valgte sine statssekretærer men ikke sine politiske rådgivere, mens statsministeren valgte både statsråder og egne politiske medarbeidere. Stoltenberg har gjentatte ganger kalt Karl Eirik Schjøtt-Pedersen, Stein Hernes, Jan Erik Larsen, Lars Erik Flatø, Rita Skjærvik, Hilde Singsaas og Mina Gerhardsen til ulike oppgaver i regjeringen. Innen markedsføring har Stoltenbergs nære venn Kjetil Try vært en mye brukt rådgiver og leverandør i valgkampanjer.
Stoltenberg har også hatt viktige politiske støttespillere i partiet som har hatt viktige verv i og utenfor regjeringen, og som tilhører samme generasjon i Arbeiderpartiet. Partimedlemmer utenfor slike fortrolige kretser, eksempelvis Oslo LO-leder Kleiv Fiskvik, har kritisert spesielt «Kristiania Forum» som et lukket miljø av nære Stoltenberg-støttespillere som Rune Bjerke, Kjell Roland, Libe Rieber-Mohn og Jon Hippe.
Samtidig hadde Stoltenberg under lederstriden mot Jagland fått motstand av LO-leder Yngve Hågensen, og la som partileder stor vekt på å konsultere fagbevegelsen, partisekretær Martin Kolberg, og LO-leder Gerd-Liv Valla - sistnevnte relasjon er omtalt og belyst i en rekke bøker. Ved valgene i 2005 og 2009 var støtten fra LO svært viktig, og Stoltenberg trakk den selv frem i valgtaler og debatter.

Jens Stoltenbergs andre regjering

Etter stortingsvalget 12. september 2005, hvor Arbeiderpartiet gikk betydelig fram, annonserte Stoltenberg at Arbeiderpartiet, Sosialistisk Venstreparti og Senterpartiet tok sikte på å danne regjering. De tre partiene startet forhandlinger på Soria Moria Hotell og konferansesenter den 26. september, og avsluttet med en pressekonferanse 13. oktober der regjeringserklæringen ble presentert. Erklæringen har senere fått navnet Soria Moria-erklæringen.
Stoltenbergs andre regjering, oftest kalt «Den rødgrønne regjeringen», tiltrådte 17. oktober 2005 under Stoltenbergs ledelse og etterfulgte Kjell Magne Bondeviks andre regjering. I regjeringen hadde Arbeiderpartiet 10 statsråder, SV hadde 5 og Senterpartiet 4. Stoltenberg valgte Jonas Gahr Støre som utenriksminister. Finansminister ble Kristin Halvorsen, den første i norsk historie som samtidig er både partileder og finansminister.
Etter tiltredelsen lå regjeringen etter opposisjonen på flere meningsmålinger. Under finanskrisen minket gapet, og det var lenge dødt løp mellom den rødgrønne og den borgerlige blokken. Særlig Stoltenberg og daværende finansminister Kristin Halvorsen steg vesentlig på tillitsmålingene.
Ved stortingsvalget 2009 gikk Arbeiderpartiet ytterligere frem under Stoltenbergs ledelse, og fikk 35,3 % av stemmene. Tross tilbakegang for Sosialistisk Venstreparti, fikk flertallsregjeringen fornyet tillit og fortsatte i den nye stortingsperioden, med visse endringer av mannskap. Etter valget i 2009 ble antall SV-statsråder redusert fra fem til fire, det samme antallet som Senterpartiet fikk. 
Etter stortingsvalget i 2009 besto Stoltenbergs regjering av statsminister, utenriksminister og 18 statsråder. Under denne regjeringen ble statssekretærposten som stabssjef ved Statsministerens kontor som forberedte regjeringsmøtene og R-notatene, og koordinerte politisk avklaringsarbeid mellom departementene, erstattet av en ny statsrådstilling uten portefølje, bekledd av Karl Eirik Schjøtt-Pedersen. Regjeringsmedlemmene ble bistått av 43 statssekretærer og 19 politiske rådgivere. Regjeringens underutvalg besto opprinnelig av partilederne for de tre regjeringspartiene. Etter at SV valgte Audun Lysbakken, som ikke satt i regjeringen, til leder, møtte Bård Vegar Solhjell som representant for SV i utvalget. I underutvalget møtte også politisk ledelse i Finansdepartementet hyppig. Fra oktober 2009 var Sigbjørn Johnsen finansminister, og dermed besto regjeringen av ikke mindre enn fire tidligere finansministere.

Økonomisk politikk og krisehåndtering

Stoltenberg er personlig sterkt engasjert i den økonomiske politikken og inntok under finanskrisen en rolle internasjonalt for å fremme internasjonalt finansielt samarbeid både gjennom Det internasjonale pengefondet (IMF)
og gjennom Sosialistinternasjonalen. Under et møte i Chile 27-29. mars 2009 møttes sosialdemokratiske ledere fra hele verden til «Progressive Governance Conference», like forut for det første G20-møtet om finanskrisen. Visepresident i USA Joe Biden var blant delegatene, og i panelet som skulle stake ut veien ut av finanskrisen, satt verten Michelle Bachelet, Storbritannias finansminister Gordon Brown, Brasils president Lula da Silva, og statsminister Stoltenberg.
Et hovedpoeng for Stoltenberg er å unngå mellomkrigsårenes og 1970-tallets ukoordinerte krisehåndtering hvor de ulike landene svekket hverandre snarere enn å samarbeide. I september 2010 innkalte Stoltenberg et globalt toppmøte for å drøfte hvordan sysselsetting og vekst kan oppnås internasjonalt i kjølvannet av finans- og gjeldskrisen – Oslo Conference E 2010 – ledet av ILO-leder Juan Somavia og IMF-sjef Dominique Strauss-Kahn. 
I sin tale holdt Stoltenberg fra første stund frem de enorme kostnader krisen hadde fått i form av arbeidsløshet, og appellerte til bedre internasjonal koordinering, balanse mellom innstramming og økonomisk vekststimulans, aktive arbeidsmarkedstiltak for unge, og investeringer for økt innovasjon.
Et eget krisemøte i De europeiske sosialdemokratenes forum (PES) ble samlet i Oslo i mai 2011, på initiativ fra Stoltenberg og tenketanken Policy Network. PES trakk spesielt frem Stoltenbergs innlegg i oppsummeringen av konferansen.

Det rødgrønne prosjektet

Ved dannelsen av den rødgrønne regjeringen i 2005 gikk Arbeiderpartiet for første gang på seksti år i koalisjon med andre partier. Samarbeidet med Sosialistisk Venstreparti satt dypt inne for mange i Arbeiderpartiet, og så sent som under Thorbjørn Jagland ble et slikt samarbeid ansett som relativt uaktuelt. Også Stoltenberg var opprinnelig skeptisk til organisert samarbeid med SV og Senterpartiet; han foretrakk Kristelig Folkeparti som partner, ikke minst på grunn av EU-spørsmålet. 
Tanken modnet imidlertid i opposisjonsårene 2001–2005, ikke minst gjennom tett dialog mellom Stoltenberg og SV-leder Kristin Halvorsen om et nytt, formalisert politisk flertall, hvor også Senterpartiet inngikk. Dette medførte at det rød-grønne regjeringsalternativet kunne presenteres allerede før stortingsvalget i 2005, og de tre partiene la fram en liste over 101 politiske områder hvor de var enige.  
Stoltenbergs andre regjering ble i 2009 den første norske flertallsregjeringen på 40 år som ble gjenvalgt, og den første siden Brundtland III (1993) til å bli gjenvalgt. Likevel er det en kjensgjerning at Stoltenberg personlig også ønsker Kristelig Folkeparti med i det langsiktige, politiske flertallsgrunnlaget på ikke-borgerlig side.

Internasjonalt klimaarbeid

Et viktig forslag fra Stoltenberg-regjeringen, og et personlig engasjement fra statsministeren selv, er samarbeid med tropiske land om å bevare mer av deres regnskog for å binde karbondioksid (CO₂) og slik redusere skadelige klimagassutslipp som gir global oppvarming. I 2007 fikk regjeringen støtte fra opposisjonen til en langsiktig avtale om å finansiere skogsbevaring med 3 milliarder kroner hvert år. Stoltenbergs regjering tok initiativ til og støttet de innenlandske klimakuttene som ble fremforhandlet med Klimaforliket i Stortinget i 2008, som et tverrpolitisk grunnlag for norske forhandlingsposisjoner internasjonalt. Statsministeren legger samtidig vekt på at internasjonale avtaler med globale avgifter eller kvoter er det mest effektive virkemidlet for å redusere klimagassutslippene. Forut for FNs klimakonferanse 2009 i København markerte Stoltenberg seg sterkt som talsmann for bevaring av regnskog. Et eget forslag om bevaring av regnskog med finansiering fra rike land, ble fremmet av Stoltenberg og Brasils president Lula da Silva i 2009, og oppnådde støtte blant andre fra USAs president Barack Obama under COP15 i København.
Toppmøtet i København endte uten en forpliktende avtale, men foran det påfølgende COP16 i Cancún etterfulgte Stoltenberg Storbritannias statsminister Gordon Brown i ledervervet for komiteen som arbeider med finansiering av klimatiltak i fattige land, som ellers bestod av Etiopias statsminister Meles Zenawi. Under en egen skogs- og klimakonferanse i Oslo i mai 2010 ble forslag presentert for en rekke land, med endelig avlevering av finansieringsrapporten høsten 2010. Et norsk forslag om et eget, globalt finansieringstilak for regnskog ble presentert med fokus på Brasil, Indonesia og det sentrale Afrika.

Vaksinasjon av barn

Stoltenberg er opptatt av at alle verdens barn skal bli vaksinert mot smittsomme sykdommer. Det første foredraget han holdt i sin andre periode som statsminister var på Farmasidagene 2005 under tittelen «Vaksinasjon mot fattigdom». Stoltenberg var styremedlem i Det internasjonale vaksinefondet (GAVI) 2002–2005 og ble tildelt Barnehelseprisen i 2005.
Et internasjonalt initiativ, med Storbritannia, Gates Foundation og Norge i spissen, sikret den 13. juni 2011 at Den globale vaksinealliansen (GAVI) fikk mer enn 3,7 milliarder dollar frem til 2015 til sitt arbeid mot barnedødelighet. Stoltenberg var en av de sentrale pådriverne bak initiativet, og har understreket at dette er et viktig bidrag for å redde 9 millioner barn fra å dø av de vanligste barnesykdommene.
I sin nyttårstale 1. januar 2013 snakket Stoltenberg om hvordan vaksinering av verdens barn er en personlig hjertesak. «Små sprøytestikk gir millioner av barn hele livet i gave. Et strøk salve kan redde mor. At så mange mødre og barn får leve, mener jeg er et mirakel i vår tid.», sa statsministeren.

Medaljeutdeling på Veterandagen

Den 8. mai 2011, da veteranene Trond André Bolle, oberst Eirik Johan Kristoffersen og kaptein Jørg Lian ble tildelt Krigskorset, den først tildeling av denne medaljen siden andre verdenskrig, var det overraskende Stoltenberg som stod for medaljeutdelingen og ikke kong Harald V. Dette ble reist kritikk og både Stoltenberg og Kongen beklaget «misforståelsen», og forsikret at det var enighet mellom kongehuset og Stortinget om hvordan seremonien skulle foregå. Videre utelukket ikke Stortinget at det er Kongen som skal dele ut Krigskorset i fremtiden. Flere kommentatorer og forskere trakk frem at Stoltenberg ikke så det politiske sprengstoffet i symbolsaker, eller at han fikk dårlige råd av folk rundt seg.

Terrorangrepene i 2011

Da Anders Behring Breivik sprengte en bombe i regjeringskvartalet 22. juli 2011, arbeidet statsministeren med årets Utøyatale i sin bolig i Parkveien. Statsministeren tok umiddelbart del i kriseledelsen, kommunikasjon med media og utenlandske ledere, og formidlingen av den nasjonale sorgen over de mange ofrene for terroren. Hans første meddelelse kom like etter angrepene, hvor han orienterte i fjernsyn om at landet blir styrt og regjeringen er i arbeid. Stoltenberg selv kjente flere av de som senere ble drept i massedrapene på Utøya. I sin første tale etter terrorangrepene understreket Stoltenberg at svaret på vold er enda mer demokrati, og enda mer humanitet, men aldri naivitet: «Vi er en liten nasjon, men vi er en stolt nasjon. Ingen skal få bombe oss til taushet. Ingen skal få skyte oss til taushet. Ingen skal noensinne få skremme oss fra å være Norge», uttalte Stoltenberg i sin tale samme dag.
Under sørgemarkeringen i Oslo hvor 200 000 mennesker deltok den 25. juli, uttalte Stoltenberg at «Ondskap kan drepe et menneske, men aldri beseire et helt folk.» Han besøkte i disse dagene AUFs sommerleirdeltagere på Sundvollen, talte i minnegudstjenesten i Oslo domkirke, og deltok tidlig i august i begravelser for Utøya-ofre. Både kong Harald og Stoltenberg høstet fem dager etter hendelsen stor tillit for måten de opptrådte under og etter terrorhendelsene. TV 2s politiske redaktør Stein Kåre Kristiansen mente i denne sammenhengen at Stoltenberg som første statsminister siden Einar Gerhardsen, nærmer seg en posisjon som «landsfader», mens tidligere Oslo-biskop Gunnar Stålsett uttalte at «Det er ikke mange statsministre gjennom tidene som har vært satt på en slik prøve. Ikke alle ville klart det på samme måte. For et land å ha en statsminister som kan virke så samlende er et privilegium.»
Også politiske motstandere roste Stoltenberg for ledelsen under terrorkrisen. Siv Jensen uttalte: «Jens Stoltenberg har i denne situasjonen vært statsminister for alle, han har også vært min statsminister. Stoltenberg har hatt evnen til å stå oppreist i en veldig vanskelig tid og kommet med gode ord.»
I etterkant av terrorangrepet nedsatte Stortinget og regjeringen henholdsvis 22. juli-komiteen og 22. juli-kommisjonen, eller Gjørv-kommisjonen, for å granske forløpet. Rapporten fra 22. juli-kommisjonen ble offentliggjort 13. august 2012. Rapporten berømmet blant annet helse- og redningsarbeidet og regjeringens kommunikasjon til befolkningen. Rapporten kritiserte politiets utrykningstid, PSTs forarbeid og statens manglende oppfølging av «allerede vedtatte sikringstiltak.» Som en følge av 22. juli-kommisjonens funn ble en politianalyse, med forslag til omorganiseringer i Politi- og lensmannsetaten, avlevert den 19. juni 2013. Stoltenbergs siste år som statsminister ble således preget av forvaltnings- og sikkerhetspolitiske debatter.

Stoltenberg som taler og debattant

Stoltenberg er som fagmann på hjemmebane innen økonomi, og var nok lenge hemmet av å bli oppfattet som fagmann. Retorikkekspertene Anders Johansen og Jens Kjeldsen karakteriserte i 2005 Stoltenberg som «en politiker som taler saklig - og sjelden om seg selv. Likevel er interessen for hans person kolossal». De bruker sluttappellen i lokalvalgkampen i 2003 som eksempel, en debatt som gikk bare få dager etter drapet på Anna Lindh i Sverige. I stedet for å appellere til å stemme på Arbeiderpartiet, ba Stoltenberg folk om å bruke stemmeretten og bevare demokratiet. Ekspertene mener her at Stoltenberg forsøkte å heve seg over det partipolitiske kivet og «taler ikke som politiker, men som statsmann.» Denne typen argumentasjon er derimot viktigere for Ap enn for andre partier fordi lav valgdeltagelse særlig rammer Arbeiderpartiet. Og siden 2005 har Stoltenberg fortsatt en utvikling i retning av en mer personlig og emosjonell stil, med økt bruk av humor og småhistorier. 
Stian Bromark og Dag Herbjørnsrud trekker frem et eksempel fra Arbeiderpartiets landsmøte i 2005, hvor Stoltenbergs kommenterte nedleggingstrusselen mot Oslo katedralskole slik:
«Skolen har overlevd Svartedauden, 400-årsnatten under danskene, nødstiden under Napoleonskrigene, unionstiden med Sverige, første og annen verdenskrig. Men det er høyst usikkert om den overlever Kristin Clemet og Kjell Magne Bondevik". Latteren jallet gjennom salen.»
Retorikkeksperten Kjell Terje Ringdal analyserte Stoltenbergs tale på Rådhusplassen 25. juli 2011, tre dager etter terroranslaget mot Oslo og Utøya. Ringdal karakteriserte talen som «den viktigste tale holdt i Norge siden krigen», og trakk frem at Stoltenbergs tidligere budskap om demokrati ble fremført med enda større «intensitet og varme» enn tidligere. I tillegg til å være retorisk riktig la Ringdal til: «Samtidig er talen typisk for Jens Stoltenberg. Han er seg selv. Andre ville kanskje brukt flere bilder og et mer poetisk språk. Dette er en veldig konkret og varm tale som kler Stoltenbergs stil, og vi kjenner ham igjen, som en rasjonalist, men også som en medfølende politiker.»

Generalsekretær i NATO

Den 28. mars 2014 offentliggjorde NATO at Stoltenberg var valgt til Anders Fogh Rasmussens etterfølger som generalsekretær og leder av Det nordatlantiske råd. Han tiltrådte stillingen den 1. oktober 2014. Stoltenberg fikk i 2017 forlenget sin periode som generalsekretær til 2020. Den 28. mars 2019 ble det kunngjort at Stoltenbergs verv som generalsekretær var blitt forlenget med to år, slik at han vil være i funksjonen til 30. september 2022. Da vil bare Joseph Luns ha sittet lenger som generalsekretær i Nato.

Utmerkelser

I 2003 ble Stoltenberg tildelt Årets europeer på Europeisk Ungdoms landsmøte 2003. I 2016 ble han tildelt Kong Harald Vs jubileumsmedalje 1991–2016.