Один из известных фарерских футболистов, много сезонов был основным вратарём клуба «ХБ Торсхавн», в составе которого трижды становился чемпионом Фарер: 1988, 1990, 1998. Cыграл рекордное количество матчей в истории клуба - более 300. В 1991-1992 годах провёл за национальную сборную Фарер 4 матча, в том числе в отборочных турнирах Евро-92 (второй тайм против будущих победителей турнира,сборной Дании) и чемпионата мира 1994 года (полные матчи против Бельгии и Кипра). Находясь в тени более известного широкому кругу болельщиков Йенса-Мартина Кнудсена, Йоханнесен восемнадцать матчей фарерской сборной провёл на скамейке в роли незадействованного запасного голкипера, в том числе, в состоявшейся 12 сентября 1990 года памятной многим игре отборочного турнира Евро-92, когда дебютировавшие в международных турнирах фарерцы преподнесли большой сюрприз, обыграв сборную Австрии со счётом 1:0.
Кай-Лео Йоханнесен стал первым в истории человеком, игравшим за футбольную сборную, который впоследствии возглавил правительство. Справедливости ради, следует заметить, что Фарерские острова политически не являются полностью суверенным государством, при том, что они обладают исключительно широкой автономией в составе Датского королевства. Любопытно, что возглавляемая Йоханнесеном Юнионистская партия как раз выступает против провозглашения Фарерами государственной независимости, о чём на расположенном в Северной Атлантике архипелаге с населением 48 тысяч человек ещё со времени окончания второй мировой войны ведётся активная политическая борьба.
Любопытно отметить, что в мировой истории дважды бывали случаи, когда бывшие игроки национальных футбольных сборных были близки к тому, чтобы стать политическими лидерами своих стран. В 1980 году Альберт Гудмундссон проиграл президентские выборы в Исландии Вигдис Финнбогадоттир, а в 2005 году Джордж Веа в упорной борьбе уступил на аналогичных выборах в Либерии Элен Джонсон-Серлиф. Причём, в обеих случаях речь шла о самых первых женщинах-президентах, соотвестственно, в Европе и Африке.
По мнению многих местных наблюдателей, Йоханнесен в роли премьер-министра во многом является компромиссной фигурой, так как он по своему политическому весу уступает председателям других коалиционных партий - бывшему премьеру, социал-демократу Йоаннэсу Айдесгорду ("Явнаарфлоккурин") и представителю буржуазной Народной партии Ёргену Никласену ("Фолькафлоккурин"), а также лидеру оппозиции, республиканцу Хёгни Хойдалю ("Чёвельди").
Женат, трое сыновей.