Paul began his playing career in 1991 playing as a Prop for Leeds. He made two appearances for Great Britain under-21's between 1992 and 1993 while at Leeds. He spent the majority of his career at the Bradford Bulls, where he established himself as a Bradford and Great Britain stalwart. In 2005, Anderson moved to St. Helens. On 10 May 2006, the BBC announced that Paul Anderson would retire from playing in order to be an assistant coach with Huddersfield Giants beginning in the 2007 season. On 16 July 2012 Anderson was announced as the new Head Coach after Nathan Brown's removal from the position. Anderson had been due to assume the role at the end of the 2012 Super League season but this was brought forward with Brown leaving early after a downturn in form and his decision to assume the job of Head Coach at St Helens for the 2013 season.
Anderson won caps for England while at Bradford Bulls in 2000 against Australia (sub), Fiji, Ireland, and New Zealand (sub), in 2001 against Wales, and won caps for Great Britain while at Bradford Bulls in 1999 against Australia (sub), in 2001 against France (sub), and Australia (sub) (3 matches), in 2002 against New Zealand (sub) (3 matches), and in 2003 against Australia (sub) (2 matches).