Paul only had a brief spell at Carrow Road; joining the Canaries from Wigan in May 1988 for £73,000 and leaving for Wolverhampton Wanderers in December 1989. Faced with competition with Ruel Fox and Jeremy Goss on the right side of the Norwich midfield, Paul was limited to just eight appearances, four of which were as substitute.

After approximately 200 games for Wolves, Paul moved to the top flight with Coventry City. 37 appearances followed before a move down one division with Tranmere Rovers in March 1996 for £250,000. In October 1997 he joined Gary Megson's Stockport County for £250,000 and scored on his debut.

Paul joined Burnley on loan on 25th March 1999. Impressing in his 12 games for the Clarets, Cook eventually signed for Burnley in early July 1999 on a free transfer. By the end of the 2000/01 season, Paul had made 96 league appearances for Burnley scoring 7 goals. Paul spent December 2001 on loan to Wigan Athletic.

Returning to Burnley, Paul made many more appearances to take his total to almost 200 games. Out of contract at the end of the 2002/03 season, he announced in April 2003 his retirement from the professional game. He was persuaded otherwise by Accrington Stanley preparing for their first season in the Conference who signed him in late May 2003 Paul is now primarily working as a coach for Stanley and was part of their management team that led them to promotion to the Football League in April 2006 after 44 years away.

In June 2006, he was appointed as Southport's first ever full-time manager, replacing Liam Watson. He lasted in this role until 3rd January 2007, departing the club after a run of three straight defeats over Christmas 2006 left them bottom of the Conference. Cook's Southport had managed just four wins in the first half of the season.

Paul Cook was named as the new Sligo Rovers manager on April 27th 2007, taking over from Rob McDonald