Nuttall won the seat of Sandgate at the 1992 state election as the Labor candidate, succeeding the retiring former Labor Opposition leader, Nev Warburton. He was previously an organiser for the Electrical Trades Union.
He served in the Beattie Ministry as:Parliamentary Secretary to the Premier with special responsibilities for Multicultural Affairs (29 June 1998 – 17 February 2001);
Minister for Industrial Relations (22 February 2001 – 12 February 2004);
Minister for Health (12 February 2004 – 28 July 2005); and
Minister for Primary Industries and Fisheries (28 July 2005 – 7 December 2005).
In 2004 he attempted to become Deputy Premier with a plan to overthrow the Premier at the time, Peter Beattie. However, a leadership challenge received no support from then Deputy Premier Anna Bligh, whom Nuttall proposed as the new Premier. Ms Bligh later said, "I didn't see it as any serious proposition that would have received any support from my colleagues and it didn't receive any support from myself."
In July 2005, he resigned as Minister for Health following media exposure of problems at Bundaberg Base Hospital. In June 2010, following a number of investigations, the hospital's director of surgery, Jayant Patel, was convicted and jailed for seven years on three counts of manslaughter and one count of grievous bodily harm to patients in his care. Nuttall blamed the system he had inherited as well as the administrators at the hospital for the situation which had arisen, but ultimately stepped down from the health portfolio. Premier Peter Beattie opted to take over the portfolio himself, relocating Nuttall to the primary industries and fisheries portfolio.
In August 2005, Nuttall stepped aside from the Ministry while the Crime and Misconduct Commission (CMC) investigated claims he had given a false answer to a Parliamentary estimates committee regarding his prior knowledge of problems with overseas-trained doctors. The Commission reported back in December 2005, recommending the Attorney-General prosecute Nuttall under section 57 of the Criminal Code. The prosecution was not proceeded with; the government decided to revoke the relevant section of the Criminal Code so Parliament could deal with such matters itself under contempt of parliament provisions.
Nuttall resigned from the Ministry on 7 December 2005 and retired from Parliament at the September 2006 election. He resigned from the Labor Party on 12 December 2006 before he was referred to the party's Disputes Tribunal, which could have expelled him.
In 2006 the CMC also began an investigation into a series of loans Nuttall received from Queensland mining magnate Ken Talbot. On 19 January 2007, the CMC charged Nuttall with 35 counts of corruptly receiving payments totalling almost $300,000 from Talbot between 2002 and 2005. Nuttall was later charged with receiving a further secret commission of $60,000 in 2002 from businessman and WorkCover Queensland director Harold Shand. Talbot and Shand were also charged over the alleged secret commissions.
Nuttall was committed to stand trial in December 2008. In June 2009, he pleaded not guilty to all charges before the District Court. On 15 July 2009, a jury convicted him on all 36 charges, and on 17 July he was sentenced to seven years' jail with a non-parole period of two and a half years.
Ten years earlier, on 12 May 1998, Nuttall said of his benefactor, Talbot, in Parliament,
I now turn my attention to ... one Mr Ken Talbot, the chairman of Sunrise Mining (Queensland) Pty Ltd. Mr Talbot has an interesting track record. He is a former senior employee of Bond Coal, led by one Alan Bond, who, of course, is currently serving a jail term for white collar fraud. Honourable members do not need to be reminded of the very close and personal links that existed between the now disgraced Mr Bond and his close associates, of whom Mr Talbot was one, and the corrupt National Party Government that was thrown out of office in 1989. Nor do honourable members need reminding of the days of deals done in brown paper bags between corrupt National Party figures and shady businesspeople of the ilk of Mr Talbot and Mr Bond.
On 14 August 2009, Nuttall lodged an appeal against his July 2009 conviction and sentence. On 12 February 2010, his appeal against conviction and sentence was heard in the Supreme Court of Queensland. On 23 March 2010, his appeal against conviction was dismissed, and his application for leave to appeal against sentence was refused.
In August 2010, the charges against Talbot were dropped due to his death in a light plane accident. In 2011, Shand was convicted of paying Nuttall a secret commission and sentenced to 15 months jail.
On 16 July 2009, the CMC recommended 10 new charges relating to alleged secret cash payments to Nuttall totalling $152,700 from businessman Brendan McKennariey, between December 2001 and April 2006, regarding a government-funded project subcontracted to McKennariey. Nuttall was also charged with five counts of perjury relating to his evidence at a CMC closed hearing.
On 11 October 2010, in the Brisbane District Court, Nuttall pleaded not guilty to five charges of official corruption, five alternate charges of receiving secret commissions and five counts of perjury. On 12 October 2010, McKennariey gave evidence for the Crown. On 27 October 2010, a jury found Nuttall guilty of five charges of official corruption and five charges of perjury. On 16 December 2010, he was sentenced to a further five years imprisonment. On 17 January 2011, the Queensland Government announced it would appeal the "inadequacy" of the sentence. The appeal was heard in the Queensland Court of Appeal on 10 May 2011. On 7 June 2011, the appeal was upheld and an extra two years jail was handed down, extending his non-parole period to July 2015.
On 12 May 2011, Nuttall was brought before the bar of parliament to answer 41 charges of contempt of parliament for non-disclosure, as a member of parliament, of pecuniary interests totalling $368,866.55. Parliament found him to have been contemptuous and fined him $82,000.
On 24 September 2009, the CMC commenced actions in the Supreme Court of Queensland under Queensland's Criminal Proceeds Confiscation Act 2002 to seize a property owned by Nuttall at Woodgate, near Bundaberg, having already initiated action to seize another property at Sandgate. On 12 July 2010, the Supreme Court ordered Nuttall to repay $454,000 deemed to be "proceeds of crime" to the state of Queensland and was also ordered him to pay the Government's legal costs of $42,000. The legal principle for the property seizure is known colloquially as the proceeds of crime. As at July 2016 the Queensland government launched proceedings to reclaim Nutall's pension scheme account.