Info:
Der Sohn des Organisten Kristoffer Kleive und Bruder des Organisten Iver Kleive wuchs in Skien auf. Er studierte in Oslo an der Musikkhøyskolen. Von 1981 bis 1983 war er Mitglied der Rock-Jazz-Band Lotus, daneben von 1981 bis 1984 der Band Oslo 13. 1983 erschien sein erstes Album Anti-Therapy.
Ab 1983 spielte er in verschiedenen Jazzformationen, unter anderem mit dem Anne-Marie Giørtz Quintet, dem Quartett von Frode Alnæs und Nils Petter Molvær, dem Brødrene Balke Etno Funk, dem Knut Riisnæs Quartet und Terje Rypdals Trio The Chasers. Daneben hatte er eine eigene Band mit Sidsel Endresen. In den späteren 1980er Jahren arbeitete er mit der schwedischen Gruppe Entra Live, erneut mit der Gruppe Oslo 13 und mit Trio 87. 1989 wurde er von der Norwegischen Jazzmusikervereinigung zum Jazzmusiker des Jahres gewählt.
In den 1990er Jahren stand die Zusammenarbeit mit Jon Balke und Per Jørgensen im Vordergrund, er gehörte ab 1993 auch Jon Balkes Magnetic North Ensemble an. Daneben arbeitete er im Quartett mit Nils Petter Molvær, Jens Bugge Wesseltoft und Bjørn Kjellemyr und spielte von Jon Eberson das Album Music for Men and Machines ein. Außerdem trat er auch mit Musikern wie Per Husby, Jan Gunnar Hoff, Marilyn Mazur, Gunnar Andreas Berg, Bugge Wesseltoft und Bendik Hofseth sowie mit David Murray und Pierre Dørge (The Jazzpar Prize, 1991) auf.
1996 spielte Kleive mit Olga Konkova und Carl Morten Iversen das Album Going with the Flow ein, seit 2000 arbeitet er im Trio mit Samuli Mikkonen und Anders Jormin (Wikipedia).