The improvising collective  Stavanger Kitchen Orchestra was co-founded by Nils Henrik Asheim and fellow musicians in 2005. He appears freqently with the orchestra as keyboard player, project leader, or as Master of Ceremonies for their legendary Christmas Concert.

Nils Henrik's largest project with Kitchen Orchestra until now has been the Sound Safari at the opening of Stavanger Concert Hall.

Kitchen Orchestra is organized as a musicians' pool including more than 25 musicians) in the free-jazz/contemporary improv tradition.

Kitchen appears with various leaders. The list of guest leaders up to now includes Lotte Anker, Evan Parker, Keith Tippett, Franz Hauzinger, Dave Kane and Alexander von Schlippenbach.

Internal leaders such as Didrik Ingvaldsen, Petter Fadnes, Gunhild Seim and Nils Henrik Asheim regularly take turns in coaching projects.

Kitchen hosts a yearly festival/happening called "What's Cooking", at Tou Scene, Stavanger.