22. juli 2011 ble kontorene til regjeringen i Oslo sentrum angrepet med en bombe. På Utøya i Buskerud ble mange ungdommer og noen voksne skutt og drept på sommerleiren til AUF. Til sammen ble 77 personer drept i angrepene.
Etter terrorangrepene holdt Stoltenberg en tale på TV. Han sa blant annet at «Svaret på vold er enda mer demokrati, enda mer åpenhet, men aldri naivitet.» Ingen statsministere i andre land som hadde opplevd terror, hadde snakket om det på den måten før.
I en rapport om terrorangrepene i 2012 fikk myndighetene kritikk for at de ikke hadde klart å beskytte befolkningen i Norge mot terror. Jens Stoltenberg sa at han som statsminister hadde ansvar for alt som gikk galt, men at han ville forbedre det som ikke var godt nok.