Lillestrom forması giyerken, döneminin Norveç için rekor olan bir bonservis ücreti ile 1995 yılınad Beşiktaş`a transfer oldu. Gösterişsiz futbolu ile o sezon kulübün en istikrarlı futbolcularından biri olmasına rağmen Christoph Daum`un yönettiği takım sezonu kötü bir performansla tamamladı ve Johnsen spor yazarları tarafından oldukça eleştrildi.
Ancak bu eleştrilere rağmen bir sonraki sezon Premier Lig`in en önemli takımlarından Manchester United`a transfer oldu ve 6 sezon boyunca bu takımda oynadı. 1996`dan 2002`ye kadar bu 6 senede içinde 4 lig şampiyonluğu (1997, 1999, 2000 ve 2001), bir FA Cup (1999 yılında) ve yine 1999 yılında bir kez de UEFA Şampiyonlar Ligi şampiyonluğu yaşadı.
2002 yılında Birmingham takımı Aston Villa`ya transfer oldu ve iki sezon da bu takımda forma giydi. 49 kez forma giydiği Aston Villa`dan 2004 yılında Newcastle United`a transfer oldu ancak burada ilerleyen yaşı ve fiziksel durumunun müsait olmaması nedeniyle çok az forma şansı bulabildi.
2005 yılında futbolu bırakmayı planlasa da sonradan kararını değiştirdi ve Norveç ekibi Valeranga ile sözleşme imzaladı.
Defans ve orta sahada görev yapan Johnsen, 61 kez Norveç Milli Futbol Takımı`nın forması giymiştir. 1998 FIFA Dünya Kupası`nda Norveç kadrosunda yer aldı.
Kariyeri
- } Lyn 1992 - 1993
- } Lillestrí¸m 1994 - 1995
- } Beşiktaş 1995/1996
- } Manchester United 1996 - 2002
- } Aston Villa 2002 - 2004
- } Newcastle 2004/2005
- } Ví¥lerenga 2005 -