Paul began his playing career in 1991 playing as a for Leeds Rhinos. He made two appearances for Great Britain under-21s 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 Bulls 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 played for the Bradford Bulls at prop forward in the 1999 Super League Grand Final which was lost to St. Helens. Anderson won caps for England while at the Bradford Bulls in 2000 against Australia, Fiji, Ireland, and New Zealand, in 2001 against Wales, and won caps for Great Britain while at the Bradford Bulls in 1999 against Australia, in 2001 against France, and Australia , in 2002 against New Zealand , and in 2003 against Australia . Anderson played for the Bradford Bulls from the interchange bench in their 2001 Super League Grand Final victory against Wigan Warriors. As Super League VI champions, the Bradford Bulls played against 2001 NRL Premiers, Newcastle Knights in the 2002 World Club Challenge. Anderson was selected for the interchange bench in Bradford's victory. He also played for the Bradford Bulls from the bench in their 2002 Super League Grand Final loss against St. Helens. Anderson played for the Bradford Bulls from the interchange bench in their 2003 Super League Grand Final victory against Wigan Warriors. Having won Super League VIII, the Bradford Bulls played against 2003 NRL Premiers, Penrith Panthers in the 2004 World Club Challenge. Anderson played at prop forward in Bradford's 22-4 victory. He also played for the Bradford Bulls from the interchange bench in their 2004 Super League Grand Final loss against Leeds. Anderson played for St Helens at prop forward in their 2006 Challenge Cup Final victory against Huddersfield. St Helens reached the 2006 Super League Grand final to be contested against Hull FC, and Anderson played at prop forward in Saints' 26-4 victory. In his first year of coaching at Huddersfield he earned his first piece of silverware by winning the League Leaders' Shield, the first time Huddersfield had won the trophy in over 80 years. Following a disappointing series of results at the start of the 2016 season where Huddersfield won only 4 of the first 18 games Anderson and assistant coach Kieron Purtill were sacked. In September 2016 Anderson was named as one of the two assistant coaches of the England team.
