Johannesen heeft het meeste van zijn carrière bij TB Tvøroyri gespeeld, maar heeft in de tussentijd ook bij twee Deense clubs gespeeld. Momenteel speelt hij in de tweede Faeröerse divisie bij TB.
Johannesen maakte zijn interlanddebuut voor de Faeröer in augustus 1992 in een vriendschappelijke wedstrijd tegen Israël. Hij heeft het record voor meeste interlands gespeeld voor de Faeröer, in totaal heeft hij 83 wedstrijden gespeeld en daarin heeft hij een keer gescoord.