Henriksen jugó cuatro partidos para Dinamarca durante la Eurocopa 2004, luego de lo cual terminó su carrera con la Selección Nacional.