Zu Beginn seiner Karriere spielte er in der von Jon Balke geleiteten Formation Oslo 13. Das gemeinsame Quintett mit Lotte Anker, Mette Petersen, Klavs Hovman und Ole Rømer veröffentlichte 1993 das Album Being bei Stunt Records. Einem breiten Publikum wurde er durch sein Debüt-Album Khmer (das 1997 beim Münchner Label ECM erschien) bekannt, auf dem Molvær sein ätherisches Spiel und seinen fiebrigen, heiseren Trompetenton wuchtigen elektronischen Beats gegenüberstellt. Khmer erhielt sehr viel Beachtung und hervorragende Kritiken; so bekam Molvær z. B. den Preis der Deutschen Schallplattenkritik und die amerikanische Zeitung L.A. Weekly ernannte Khmer zum Jazzalbum des Jahres 1998. Das Magazin Rolling Stone wählte das Album 2013 in seiner Liste Die 100 besten Jazz-Alben auf Platz 92.[1]
Nils Petter Molvær beim Jazzfestival in Neuwied 2001
Es folgten im Jahr 2000 das Album Solid Ether und im darauf folgenden Jahr das reine Remix-Album Recoloured, auf dem verschiedene Gastmusiker und DJs mitwirkten, darunter Bill Laswell und Funkstörung. 2002 wurde das Album NP3 und im Sommer 2004 Streamer veröffentlicht. Streamer erschien auf Molværs eigenem, neu gegründeten Label Sula. 2005 brachte Molvær dann mit ER ein weiteres Studioalbum heraus, auf dem neben ihm vor allem die Sängerinnen Sidsel Endresen und Elin Rosseland, aber auch Gitarrist Eivind Aarset und Pianist Magne Furuholmen (ehemals a-ha) wesentliche Akzente setzten.
