Paul Raymond Henderson AO (born 15 August 1962)^[1] is a former Australian politician who was Chief Minister of the Northern Territory from 2007 to 2012. He has been Chancellor of Charles Darwin University since March 2019.^[2]

Henderson was born in Croix-Chapeau, France, where his father was serving with the United States military. He was educated in the United Kingdom to A-Levels and studied mechanical engineering through the City and Guilds of London Institute. He worked as an apprentice marine fitter in Southampton before emigrating to Australia in 1982, where he worked as an underground fitter at the zinc mines in Rosebery, Tasmania. He moved to Darwin in the Northern Territory in 1983, working as a marine fitter.^[3] In 1985 he began working for the Northern Territory government as a computer operator, was self-employed as a computer analyst in Britain from 1991 to 1992 and returned to work for the Northern Territory government in 1993.

Henderson was elected to the Northern Territory Legislative Assembly in an August 1999 by-election for the Labor Party (ALP), representing the electorate of Wanguri when the previous member, John Bailey, resigned.^[4]

Henderson was promoted to cabinet in 2001 after Labor won a Territory election for the first time in 2001. He held the following ministries: Minister for Employment, Education and Training; Minister for Tourism; Minister for Public Employment; and Minister for Multicultural Affairs, until he became Chief Minister of the Northern Territory after the sudden resignation of Clare Martin on 26 November 2007.^[5] He became the first man to lead an ALP Government in the Territory.

At the 2008 territory election, Henderson lost most of the large majority he'd inherited from Martin. Partly because new electoral boundaries had been gazetted just days before the writs were issued, most of the Labor members elected in the massive Labor landslide of 2005 were unable to connect with their new constituents. Ultimately, Labor needed a paper-thin victory in Martin's old seat of Fannie Bay to retain government with 13 of 25 seats, a one-seat majority.

In August 2009, Labor MLA Alison Anderson resigned from the ALP after a disagreement with Henderson's government over housing in remote indigenous areas. The opposition Country Liberal Party moved a motion of no-confidence against Henderson, which was defeated by one vote after Henderson reached an agreement with Independent MLA Gerry Wood to support his government.^[6]

At the 2012 territory election, Henderson's government was defeated by the opposition Country Liberal Party led by Terry Mills. On 25 January 2013, Henderson resigned from the Legislative Assembly, triggering a by-election in his electorate of Wanguri.^[7] To date, Henderson is the only ALP leader who did not serve as Leader of the Opposition.

On 26 June 2013, Henderson was granted the title "The Honourable" for life by the Governor-General.^[8]