Hän oli mukana FAFO: n tutkimuksessa Gazan, Länsirannan ja Jerusalemin elinoloista. Myöhemmin hän osallistui ECONin lähetystyöhön bioteknologian alalla vuosituhannen vaihteessa.
Stoltenberg tutki väitöskirjaansa varten lapsikuolleisuutta, sosiaalista eriarvoisuutta ja avioliittoa maahanmuuttajaryhmissä. [2][3] Hän oli vieraileva tutkija Columbian yliopistossa, ennen kuin hän alkoi työskennellä Norjan kansanterveyslaitoksessa vuonna 2001. Siellä hän on työskennellyt epidemiologian osaston johtajana, apulaispääjohtaja ja nykyään sen pääjohtaja.
Stoltenbergillä on ratkaiseva rooli kansallisessa terveysrekisterihankkeessa. [4] Hankkeen tavoitteena on nykyaikaistaa Norjan terveysrekisterit. Stoltenberg oli myös kansallisen FUGE-alustan, Biobanks for Healthin johtaja, ja on nyt Biobank Norjan[5], kansallisen tutkimusbiopankkien infrastruktuurin, puheenjohtajana. Lisäksi hän on johtanut norjalaista osaa autismin syntymätutkimuksessa. [6] Hänen tutkimuksensa keskittyy autismin ja muiden hermoston kehityshäiriöiden syihin ja riskitekijöihin.
Jon Sudbø-tapaus
Stoltenbergillä oli tärkeä rooli laajan tutkimusvilpin paljastamisessa vuonna 2006. Siinä selvisi, että lääkäri Jon Sudbø oli kertonut väitöskirjassaan suuontelosyövästä faktoja, joita ei ollut tarkistanut.