2001 erschien sein erstes Soloalbum Sakuteiki, der Titel stammt von einem japanischen Werk über die japanische Gartenkunst aus dem 11. Jahrhundert. 2004 entstand in Zusammenarbeit mit Audun Kleive und Jan BangChiaroscuro. Chiaroscuro ist die italienische Bezeichnung für die Hell-Dunkel-Malerei der Spätrenaissance und des Barock. Im Dezember 2008 schließlich veröffentlichte Henriksen mit Cartography sein erstes Soloalbum bei ECM, nachdem er zuvor bereits bei rund 25 ECM-Alben mitgewirkt hatte. Mit Bang, Erik Honorè, Tigran Hamasyan und Robert Jürjendal nahm er den Soundtrack zum Spielfilm Victoria (2013) von Torun Lian auf. Auch spielte er ein Duoalbum mit Teun Verbruggen ein und gehörte seit 2005 zum Ensemble von Sinikka Langeland.
Das 2017 bei ECM erschienene Album Rímur von Trio Mediæval & Arve Henriksen wurde im Februar 2016 in der Münchner Himmelfahrtskirche aufgenommen und von Manfred Eicher produziert.[1][2] Mit Jan Bang, Erik Honoré, Samuel Rohrer und John Derek Bishop bildete er Dark Star Safari, das Quartett seit 2019 zwei Alben vorlegte.
↑Radka Toneff-pris i Molde. In: ballade.no. 17. Juli 2007, archiviert vom Original (nicht mehr online verfügbar) am 19. August 2012; abgerufen am 21. Juli 2017 (norwegisch).