Lors des élections législatives de , ses premières en tant que chef du Parti de l'union, le mouvement arrive à la deuxième place avec 20,99% des suffrages. Le Premier ministre social-démocrate Jóannes Eidesgaard, arrivé en quatrième position, parvient
à se maintenir au pouvoir en formant une coalition tripartite[2]. Cette dernière s'effondre en , et Kaj Leo Johannesen forme alors avec le Parti du peuple et le Parti social-démocrate un nouveau gouvernement dont il prend la tête[3].
En , le Parti du peuple quitte la coalition après des désaccords sur des questions liées aux investissements et à la pêche[4]. La coalition entre le Parti de l'union et les sociaux-démocrates continue toutefois sur une base minoritaire pendant plusieurs mois.
Lors des élections législatives du , le Parti de l'union arrive en tête avec 24,70% des suffrages. Kaj Leo Johannesen obtient 1 974 votes personnels sur son nom, un record[5]. Après le scrutin, il forme un second gouvernement qui associe les partis de l'Union, du Peuple, du Centre et Autogouvernement[6]. En , ce dernier quitte la coalition.
Lors des élections législatives du , la coalition sortante est largement battue, et le Parti de l'union termine passe de la première à la quatrième place[5]. Kaj Leo Johannesen annonce alors sa démission de la présidence du parti, à laquelle lui succède son vice-président Bárður á Steig Nielsen le [7],[8]. Le , le social-démocrate Aksel V. Johannesen, qui bat le record de votes personnels reçus par Johannesen, lui succède au poste de Premier ministre[5],[9].
Le , deux jours après l'annonce par le Premier ministre social-démocrate Aksel V. Johannesen de la tenue d'élections législatives le , Kaj Leo Johannesen annonce qu'il ne briguera pas de nouveau mandat de député, mettant fin à une carrière parlementaire de 24 ans[11].