After resigning from the CLP, Mills regained his old seat as an independent at the 2016 election.
Mills was born in Geraldton, Western Australia, and lived in the agricultural town of Mullewa for a time with his parents, Bernard and Patricia. He was educated at St Patrick's College, Geraldton, before moving to Perth and gaining a Diploma of Education at the Western Australian College of Advanced Education. In 1983, he commenced teaching at a private school in Perth, and in the same year married Ros (née Serich). They had one son and one daughter. In 1989, the family moved to the Northern Territory, where Mills became principal of a Christian school.
Mills joined the Country Liberal Party in the 1990s, and in a 1999 by-election, was elected to the seat of Blain in the Northern Territory Legislative Assembly. Initially, he served as Chairman of Committees. In 2001, following the defeat of the Country Liberal government, Mills assumed the shadow portfolios of Youth Affairs, Education, Employment and Training, and Sport and Recreation.
On 14 November 2003, he replaced Denis Burke as Leader of the Opposition, and assumed the portfolios of Shadow Treasurer, Asian Relations and Trade, Territory Development, Railways, Racing and Gaming. He resigned on 4 February 2005 to be replaced by Burke, who subsequently lost the 2005 election and his own seat. Mills himself suffered a 9.5 percent swing amid the massive Labor wave that swept through the Territory. He was left as the only CLP member from Palmerston, an area that has historically been a CLP stronghold. Indeed, he was the only CLP member holding a Darwin-area seat in the Legislative Assembly, and one of only two CLP members from the Top End.
Mills served as deputy opposition leader to Jodeen Carney for three years. On 29 January 2008, however, Mills asked Carney if she was willing to swap posts with him, with Mills taking over as leader and Carney becoming deputy leader. Carney turned the proposal down and instead called for a leadership spill. The vote was tied at two votes for Carney and two votes for Mills. Carney, taking a cue from the action of former Australian prime minister John Gorton in 1971, announced that a tie vote was not a vote of confidence and resigned. Mills then took the leadership unopposed on a second vote.
At the August 2008 election, the CLP increased its representation to 11 seats (from four in the old parliament), regaining much of what it had lost in its severe beating of three years earlier. This rose further in 2012 when Labor-turned-independent MP Alison Anderson, with Mills' encouragement, joined the CLP.
At the 2012 general election, the CLP won government on a four-seat swing, primarily due to a large swing in remote Aboriginal areas which had historically supported Labor. Mills was sworn in as Chief Minister of the Northern Territory on 29 August 2012.
When Mills was in opposition in 2011, he stated his support for an audit of the Northern Territory finances, saying that "[an audit] will be the start of a new era of transparency in government expenditure." However, after coming into power he changed his mind on the issue.
In February 2013, following a large swing to Labor in the Wanguri by-election, canvassing took place within the CLP to gauge support for a challenge to Mills from his Attorney-General, John Elferink. Lacking the support of key MLAs, Elferink ruled out a challenge and offered his resignation to Mills, which was declined. In early March, Mills was unsuccessfully challenged by Health Minister Dave Tollner, who was sacked from Mills' cabinet after a six-and-a-half-hour party meeting. A little over one week later, on 13 March 2013, Mills, who was overseas at the time, was ousted by Transport Minister Adam Giles in an 11–5 vote of his party's parliamentary caucus. Following the leadership change, Tollner was promoted from the back bench to Deputy Chief Minister.
Mills resigned from Parliament on 20 February 2014 which triggered the 2014 Blain by-election.
As a sop to Mills, Giles appointed him as the Territory's commissioner to Indonesia and ASEAN. When Giles was nearly ousted as Chief Minister by Mills' former deputy Willem Westra van Holthe in February 2015, Mills tweeted a picture of himself laughing in delight, prompting Giles to sack him.
Mills announced on 7 August 2016 that he had resigned from the CLP and would seek to regain his former seat of Blain as an independent at the 2016 election. He likened the Giles government to a car accident, saying, "At the scene of an accident, one has a moral obligation to render assistance." Mills finished six points behind Labor candidate and former federal MP Damian Hale on the primary vote, pushing the CLP into third place. He narrowly overtook Hale on CLP preferences, allowing him to return to the legislature after a nearly two-year absence. He joined his original Deputy Chief Minister, Robyn Lambley, on the crossbench; Lambley had left the CLP in 2015, but easily won reelection as an independent.
Ironically, at the same election at which Mills retook his old seat as an independent, the man who had rolled him as Chief Minister, Giles, became the second Majority Leader/Chief Minister to lose his own seat.