Op 20 april 2008 leidde Johnsen zijn eerste wedstrijd in de Noorse nationale competitie. Tijdens het duel tussen Aalesunds FK en Hamarkameratene (5–0) trok de leidsman eenmaal de gele en eenmaal de rode kaart.[1] In Europees verband debuteerde hij tijdens een wedstrijd tussen EB/Streymur en Kalmar FF in de voorronde van de UEFA Europa League; het eindigde in 0–3 en de Noorse leidsman gaf vier gele kaarten.[2] Zijn eerste interland floot hij op 2 september 2011, toen Litouwen met 0–0 gelijkspeelde tegen Liechtenstein. Tijdens dit duel gaf Johnsen vijf gele kaarten en één rode.[3]
Noorwegen
Litouwen – Liechtenstein 
Estland – Polen 
Denemarken – Montenegro 