Henderson made his National Rugby League premiership début for the Sydney Roosters against the Parramatta Eels in round 1 of the 2003 NRL season. After two years at the Sydney Roosters he moved to Parramatta however did not achieve more game time and left halfway through the 2005 NRL season. He is sporadically called up to don the famous colours of 'Dinner Club', representing the local third division Oz Tag team and subsequently securing eligibility for their end of season trip.
Henderson made his début for the Warriors in round 1 2008, playing against the Melbourne Storm. While a Warriors player, Henderson said Castleford, West Yorkshire was the worst place he had lived. He said that residents have rotten teeth, spend too much time drinking and need a bath.[9] All three Henderson brothers featured in the Scotland squad for the 2008 Rugby League World Cup.[10] In May 2009 the Warriors announced they had re-signed him until the end of the 2011 season.[11]
On 23 August, it was announced by the Warriors that they had released Henderson from the final year of his contract so he could sign a three-year deal with the Catalans Dragons in the Super League starting in 2011.[12]
Catalans Dragons
Henderson joined the Catalans Dragons in 2011. Henderson made 129 appearances for Catalans between 2011 and 2015. Henderson was again part of Scotland's 2013 Rugby League World Cup campaign.
Return to the Sydney Roosters
On 3 August 2015, Henderson announced his return to Australia to play for his former club, the Sydney Roosters, in 2016. Henderson's move back to the NRL ended his five-year stay in France.[13]
On 17 March 2016, Henderson suffered a broken leg in the Roosters' 0–40 defeat by the North Queensland Cowboys.[14] This eventually lead him to announcing his retirement from rugby league later in the year. In 2018, Henderson returned to Rugby League on the Central Coast leading the Kincumber Colts.
Commentary career
Henderson was a commentator at the 2021 Rugby League World Cup mainly featuring in Scotland's group stage matches as a co-commentator.[15]