Henriksen was capped 66 times for the Danish national team, and he represented his country at two FIFA World Cups and two European Championship tournaments.
He made his debut in the friendly match 1–0 win against Scotland as he came on as a substitute at half time, replacing defender Jacob Laursen.
Henriksen was an important member of the national team at the 2002 FIFA World Cup, where Denmark reached the round of 16.
[6] The 2003–04 season was Henriksen's most successful year at Panathinaikos, as the club broke rivals Olympiacos' seven-year streak when they won the 2004 Greek Super League.
Even though he did not score any goals, his elegant playing style meant he only received two yellow cards during his national team career.