Henriksen giocò per Sarpsborg, Lyn Oslo e Frigg a livello di club. Fu soprannominato Svarten.
Nazionale
Disputò 28 incontri per la Norvegia. Debuttò in Nazionale il 2 settembre 1934, nella vittoria per quattro a due sulla Finlandia. Fece parte della squadra che vinse il bronzo olimpico a Berlino 1936: fu però una riserva e non scese mai in campo nel torneo. Due anni dopo, partecipò al campionato del mondo 1938.
Allenatore
Henriksen fu allenatore del Vålerenga in due diverse circostanze: la prima volta dal 1947 al 1948 e la seconda dal 1957 al 1958. Nel 1950, fu l'allenatore del Drafn. Ricoprì anche l'incarico di commissario tecnico della Norvegia.