Tebbutt was elected to a seat on Marrickville Council in 1993 before becoming Deputy Mayor in 1995. She was appointed to the New South Wales Legislative Council filling a vacancy following the retirement of Ann Symonds in 1998. After the Carr Government was re-elected in 1999, she served as Minister for Juvenile Justice. In July 2002, Tebbutt was promoted, given responsibility for the Ministries of Community Services, Ageing, Disability Services, and Youth, whilst retaining the Juvenile Justice portfolio. In a cabinet reshuffle in early 2005, she was promoted to Minister for Education and Training. Following Premier Bob Carr's unexpected resignation 27 July 2005, and the resultant resignations of Deputy PremierAndrew Refshauge and Senior Minister Craig Knowles, the 'Triple-M' by-elections for the seats of Maroubra, Marrickville and Macquarie Fields were held on 17 September 2005. The new incoming Premier, Morris Iemma, was said to have favoured her for the position of deputy leader—and hence Deputy Premier—as having a woman in the role would have looked favourably with the electorate. However, in accordance with longstanding Labor tradition, the deputy leader is chosen by the Socialist Left faction. Tebbutt resigned from the Legislative Council on 26 August to seek election for the seat of Marrickville. Hence for the three-week period from 26 August to 17 September 2005, Tebbutt was in the unusual, though not unprecedented, position of being a Minister of the State, without being a member of parliament. Tebbutt successfully defended the seat of Marrickville for the Labor Party in her by-election. With no Liberal candidate contesting the election in this comfortably safe Labor seat, the ALP primary vote increased, though she suffered a 5.6% two-candidate preferred swing to the Greens. On 27 November 2006, Tebbutt made a gaffe during a live interview on radio Nova 96.9. Tebbutt was complaining about the lack of history knowledge of today's schoolchildren. When the announcer asked her what is the significance of Australia Day, Tebbutt replied, "Well, we celebrate Australia Day because that's the day that we became a nation. When the states joined together, the federation of Australia, and it's an important day to understand that history." When the announcer pointed out her error, she quickly backtracked: "Sorry, you've got me too early in the morning. Australia Day of course is European arrival in Australia." Tebbutt successfully held the seat of Marrickville at the 2007 election, but announced after it that she would not be a candidate for the new ministry and would return to the back bench so she could spend more time with her family. A meeting of the Left faction on 4 September 2008 saw her return to the front bench as she was elected as the Deputy Leader of the NSW Labor Party. Following the resignation of Morris Iemma and the selection of Nathan Rees as the new Premier the following day, she was sworn in as Deputy Premier of New South Wales. She was sworn in as Minister for Climate Change and the Environment and Minister for Commerce on 7 September 2008. A little over a year later, Rees was deposed as Labor leader and Premier, in favour of Kristina Keneally. Tebbutt remained as Deputy Leader and Deputy Premier under Keneally, and became Minister for Health. With Labor sinking in the polls going into the 2011 election, there was some speculation that Tebbutt would be toppled by a Green candidate. Indeed, the ABC's Antony Green predicted that Tebbutt would be defeated by Green candidate and Marrickville Council mayor Fiona Byrne. In a very tight contest that came down to less than 680 votes, Tebbutt won the seat with 50.9% of the vote on a two-party-preferred basis, suffering a swing of 8.5%. The campaign was marked by anti-Zionist protests as four months earlier, Byrne and Marrickvile Council had controversially voted to boycott Israel. There were no allegations that Tebbutt was involved in any of the anti- or pro-Zionist threats that occurred during the campaign. In November 2013, Tebbutt announced she was retiring from politics and would not contest the 2015 election.