Mills, who had been the principal of a Christian school, was first elected to the Northern Territory Legislative Assembly in 1999, representing the seat of Blain.

He was joined by two other incumbent MLAs in early 2020, allowing the Alliance to surpass the CLP as the second-largest party in the Legislative Assembly, but lost his seat at the 2020 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.

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.

In 2001, following the defeat of the Country Liberal government, he 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.

[1][2] 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.

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.

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.

[citation needed] Mills could have refused to resign as chief minister, however, was not aware of the procedures surrounding handing in commission of office.

"[8][9] Mills finished six points behind Labor candidate and former federal MP Damian Hale on the primary vote, pushing the CLP into third place.

Later that day, CLP leader Lia Finocchiaro successfully moved a motion to declare the Opposition Leadership vacant and hold a ballot to determine it.