In 2005, Randolph announced that he would run for the Florida House of Representatives from the 36th District, which stretched from Azalea Park to Oak Ridge and Eatonville, intent on challenging incumbent State Representative Sheri McInvale in the Democratic primary. However, in 2006, McInvale switched to the Republican Party, and Randolph won the primary to oppose her against Eben Cowles Self with 61% of the vote. During the general election campaign, Randolph argued that, despite McInvale's moderate views, the Republican majority in the legislature would force her to stick to the party line. He attacked McInvale for literature that she had mailed out that included a picture of Randolph at an LGBT rights event with a drag queen with text underneath saying "Wrong for our Families," which Randolph took as homophobia. McInvale was endorsed by the Orlando Sentinel over Randolph, which argued that Randolph "seems destined to be one of those loud back-benchers" who "offers little more than the Democratic Party line against school and Medicaid reform." Ultimately, Randolph defeated McInvale in a landslide with 63% of the vote. Randolph ran for re-election in 2010, facing former Orlando mayoral candidate Stephen Villard, the Republican nominee, in the general election. He campaigned on his work in energy efficiency in the legislature and his proposals to improve water systems, increase regulation on mortgage companies, and renovate older buildings to cut down on electricity costs. This time, Randolph was endorsed by the Sentinel, which praised him as a "strong champion for education" and noted that he was a "work in progress" from his first legislative session. Randolph won re-election over Villard overwhelmingly, receiving 73% of the vote. In 2010, when Orange County Commissioner Mildred Fernandez was suspended from office after she was arrested on corruption charges, Randolph applied to fill the vacant seat. Though he met with then-Governor Charlie Crist regarding an appointment to the County Commission, Crist ultimately decided to appoint Lui Damiani. Randolph ran for re-election a final time in 2010, and was opposed by realtor Greg Reynolds, the Republican nominee, and Lawanna Gelzer, an independent candidate. He campaigned on his efforts to overturn the gay adoption ban in place in the state and his opposition to the fee increases passed by the legislature, while Reynolds called for cutting regulation to create jobs. He was endorsed by the Sentinel once again, which called him out as "one of the Legislature's most principled members, who routinely manages to draw attention to risks the Legislature shouldn't be taking." Randolph ended up winning re-election handily, receiving 60% of the vote to Reynolds's 37% and Gelzer's 4%. During the 2011 legislative session, Randolph spoke out strongly against legislation that required women to undergo and view ultrasounds before terminating a pregnancy, telling a story about how viewing ultrasounds after his wife had miscarried was a traumatic experiencing, crying while he told the story. He was later criticized during a debate on union reforms, in which he argued that Republicans were against regulations, except when it came to social issues. He sarcastically suggested that his wife "incorporate her uterus" to stop Republican efforts to limit her reproductive health choices, at which point the Speaker of the House stepped in, informing Randolph that his choice of language was inappropriate, as he referenced a body part, and that he should be conscious of the fact that "young pages and messengers" were in the chamber at the time." Following the trial of Casey Anthony and the attempts of one of the jurors to sell interviews in 2011, Randolph authored legislation that would have made it a third-degree felony for jury members to receive compensation to talk about their experience during the trial within 270 days of serving on a jury. Though he was eligible to seek a fourth term in 2012, he declined to do so, both because legislative redistricting moved him into an unfamiliar district and because he planned on running to be the next Chairman of the Florida Democratic Party.
In 2012, Orange County Tax Collector Earl K. Wood, a Democrat who had held office for 50 years, died during his re-election campaign. The Orange County Democratic Party had the responsibility of selecting a replacement candidate, though Wood's name remained on the ballot, and ended up picking Randolph. He faced Republican nominee Jim Huckeba in the abridged general election, and argued that his experience on the State House Finance and Tax Committee and that he was "an expert on tax policy" best qualified him for the office, arguing, "There are actually policies in play. It isn't just an administrative office." Huckeba attacked Randolph for "taking advantage of people who don't know that Earl has died" by campaigning with Wood's name, though Randolph responded that with so little time before the campaign, he could not have run a typical campaign. In the end, Randolph defeated Huckeba handily, winning with 57% of the vote. After he was elected, but before he was inaugurated, Randolph applied for a paying position in the Tax Collector's office to ease the transition, though he was attacked by local Republicans for accepting a salary while working.
