Volleyball

Kvalheim spielte in den Jahren 1984 bis 1989 bei Arago de Sète und gewann mit dem Verein den französischen Pokal. Anschließend wechselte er innerhalb Frankreichs zu AS Cannes und wurde bis 1992 zweimal nationaler Meister. 1994 spielte er außerdem in Italien bei Sidis Baker Falconara.

Beachvolleyball

1991 bildete Kvalheim ein festes Duo mit seinem langjährigen Partner Bjørn Maaseide. Zwei Jahre später traten Kvalheim/Maaseide bei der ersten Europameisterschaft an und unterlagen erst im Finale den Franzosen Jodard/Penigaud. Das nächste EM-Turnier in Almería konnten die Norweger dann im Endspiel gegen das spanische Duo Javier Bosma und Santiago Aguilera für sich entscheiden. Außerdem gewannen sie in den ersten Jahren mehrere Open-Turniere in Miami, Marseille und Berlin. 1994/95 waren sie die FIVB Tour Champions. Bei der Weltserie 1996 verpassten sie nur in zwei Turnieren die Top Ten. Im ersten olympischen Turnier mussten sie sich Jörg Ahmann und Axel Hager geschlagen geben, bevor sie in der Verliererrunde noch einige Spiele überstanden.

1997 in Los Angeles kamen sie bei der ersten Weltmeisterschaft auf Platz 17. Im gleichen Jahr verloren sie das Finale der Europameisterschaft in Riccione gegen ihre Landsleute Vegard Høidalen und Jørre André Kjemperud. 1998 in Rhodos wiederholten sie das Ergebnis nach einer Niederlage gegen die Schweizer Brüder Martin und Paul Laciga. Während sie bei der Weltmeisterschaft 1999 nicht über den 25. Rang hinauskamen, gewannen sie als Dritter der EM in Palma ihre nächste Medaille, womit sie fünfmal bei Europameisterschaften auf dem Treppchen standen. Bei ihrer zweiten Olympia-Teilnahme 2000 in Sydney verpassten sie das Achtelfinale und belegten Platz 19. Anschließend trennten sich ihre Wege. Kvalheim spielte im folgenden Jahr noch einige Turniere mit Bard-Inge Pettersen.