Solbakken speelde tussen 1994 en 2000 in totaal 58 wedstrijden voor de Noorse nationale ploeg, en scoorde in die periode negen keer voor zijn vaderland. Hij maakte zijn debuut op 9 maart1994 in de vriendschappelijke wedstrijd tegen Wales (1-3). Hij viel in dat duel na zeventig minuten in voor aanvoerder Kjetil Rekdal. Solbakken nam met Noorwegen deel aan het WK voetbal 1998 en beëindigde zijn interlandloopbaan na het EK voetbal 2000 in België en Nederland.