Randall made his first run for office in 1993, when he ran in the safe state Labor seat of Belmont and was defeated by future opposition leaderEric Ripper. He was a member of the Belmont City Council 1993–96 before running in Swan in the 1996 election. He was initially slated to run against Deputy Prime MinisterKim Beazley. However, with Labor sinking in the polls, Beazley transferred to the slightly friendlier seat of Brand, and Randall won with a majority of 3.9 percent. He was defeated after only one term by Labor's Kim Wilkie. For the next election, Randall sought to run in Canning. The Labor incumbent, Jane Gerick, had been severely hurt by a redistribution which all but erased her majority, reducing it from 3.5 percent to only 0.4 percent. Randall was elected on a swing of 0.8 percent. Randall spent much of 2003 priming for a rematch against Gerick, but Gerick died of a cerebral brain hemorrhage in December 2003. Her replacement, Cimlie Bowden, resigned in early 2004 after accusing party insiders of undercutting her campaign. Labor then turned to former WA Deputy ALP leader Kay Hallahan, a former state MLA for Armadale, almost all of which is located in Canning. However, the instability on the Labor side crippled its chances, and Randall was reelected with a swing of 9.2 percent in his favour, technically making Canning a safe Liberal seat. Randall was re-elected to Canning at the 2010 election, defeating high-profile Labor candidate and former Labor MP, Alannah MacTiernan, though Canning was the only seat in Western Australia to record a two-party preferred swing to Labor. Randall was appointed Shadow Parliamentary Secretary for Local Government by the Leader of the Opposition, Tony Abbottin September 2010.
Controversy
On 13 February 2008, Randall was one of six Liberal MPs not present when a motion was passed unanimously apologising to the stolen generations of indigenous children between federation and the 1970s. The others were fellow West Australian MPs Wilson Tuckey, Dennis Jensen and Luke Simpkins who chose to leave the house in protest to the apology to the Stolen Generations. On 21 October 2010, Randall referred to Australia's public national broadcaster, the Australian Broadcasting Corporation, the "Gay-BC", in response to a journalist. On 15 June 2011 at a Friends of Mining lunch, Randall used the phrase 'pussy-whipped' to describe the mining industry's relationship with then-Prime Minister Julia Gillard.
On 15 September 2012 Randall travelled to Melbourne, on a trip explained as being for 'sittings of Parliament' and which cost taxpayers $5300; the Australian Parliament, however, has not sat in Melbourne since 1927.
Cairns travel
In November 2012 Randall travelled to Cairns with his wife, for which he claimed more than $10,000 in travel expenses for 'electorate business'. The week after his return he took possession of an investment property in Cairns. The West Australian state Liberal MP Rob Johnson called on Prime Minister Tony Abbott to 'dump' Randall over the trip. Prime Minister Abbott defended Mr Randall's travel claims, saying that Mr Randall was conducting 'very important discussions' with the then Chief Opposition Whip Warren Entsch. However, when quizzed by The Australian Financial Review, Mr Entsch refused to divulge the content of those discussions and admitted he did not know if they constituted "electorate business" as Mr Randall had claimed.
On 9 February 2015 Randall seconded a federal Liberal Party leadership spill motion. Simpkins stated that such a motion would give Liberal members of parliament and senators the opportunity to either endorse the Prime Minister, Tony Abbott or "seek a new direction." The spill motion was defeated 61 votes to 39.
Death
Randall was found dead in his car near the Boddington Golf Course, on 21 July 2015, having suffered a heart attack.
