Johannesen tog guld i OS på 10 000 m 1960 och på 5 000 m 1964. Han vann VM 1957 och 1964 samt EM 1959 och 1960. Johannesen har 21 distanssegrar i VM och EM 1955–64 och satte fyra världsrekord 1960–63.