Nesbø urodził się w Oslo, a wychował w Molde. Jako młody chłopak grał w klubie piłkarskim Molde FK, ale zerwał więzadła i postanowił zrealizować się w innych dziedzinach. Nesbø pisze głównie powieści kryminalne, jest także autorem tekstów w zespole Di Derre, w którym gra i śpiewa.
Nesbø jest autorem cyklu powieści kryminalnych, w których głównym bohaterem jest policjant Harry Hole. Za swą debiutancką powieść Człowiek-nietoperz (norw. Flaggermusmannen) Nesbø otrzymał literacką Nagrodę Rivertona oraz Szklany Klucz, obydwie przyznawane za najlepsze powieści kryminalne. Z kolei za powieść Czerwone gardło (norw. Rødstrupe) otrzymał w 2000 nagrodę norweskich księgarzy. W 2004 książka ta została wybrana najlepszym norweskim kryminałem wszech czasów (norw. Tidenes beste norske krim). W 2007 powieść Czerwone gardło pojawiła się jako kandydatka do nagrody Złotego Sztyletu za najlepszą powieść kryminalną, przetłumaczoną na język angielski.
Powieści Nesbø tłumaczone były na angielski, czeski, duński, fiński, francuski, litewski, niderlandzki, niemiecki, polski, portugalski, rosyjski i szwedzki.