Onder leiding van bondscoach Egil "Drillo" Olsen maakte Johnsen zijn debuut voor het Noors voetbalelftal op 8 augustus1991 in het oefenduel tegen Zweden (1-2) in Oslo. Hij viel in dat duel na 74 minuten in voor Gunnar Halle. Johnsen speelde in totaal 61 interlands en scoorde twee keer voor zijn vaderland. Hij nam met zijn vaderland deel aan het WK voetbal 1998 in Frankrijk, waar de Noren in de achtste finales werden uitgeschakeld door Italië.