Johnsen begon bij Tiller IL en kwam begin 2013 in de jeugdopleiding van Rosenborg BK.[1] Per januari 2015 maakte hij de overstap naar het Nederlandse sc Heerenveen. In het seizoen 2016/17 zat hij al enkele keren op de bank bij het eerste team.[2] In de voorbereiding op het seizoen 2017/18 maakte hij definitief de stap naar het eerste team van Heerenveen maar vlak voor aanvang van de competitie werd hij door Ajax gecontracteerd. Ajax betaalde ongeveer 2 miljoen euro voor Johnsen.
In het seizoen 2019/20 speelde hij op huurbasis voor PEC Zwolle[4] In juni 2020 ondertekende hij een vierjarig contract bij Venezia dat uitkomt in de Italiaanse Serie B.