Paul began his footballing career at Watford as an Associate Schoolboy, Apprentice and eventually as professional under Graham Taylor's first regime at Vicarage Road. He made his debut for the Hornets in May 1983 against Liverpool and went on to make himself a regular the following season. Injury towards the end of 1984 kept him out of action for many months. Loan spells with Shrewsbury and Swindon preceded a 1987 free transfer to Reading. However further problems with his knee led to an early retirement.

Moving into non-league football, he joined Wycombe in July 1989 and became captain after Martin O'Neill's arrival the following February. At the end of that season, he joined Martin's coaching staff which eventually led Wycombe into the Football League. Paul followed Martin to Norwich in July 1995 and then to Leicester the following December. However he did act as caretaker manager for Norwich in their League Cup victory over Bolton in between O'Neill's departure and Paul's own decision to join him at Leicester.

Paul returned to Norwich in October 2000 taking up a joint management role at Eastern Counties side Norwich United. In 2005/6 he led the Norwich United side to the Norfolk Senior Cup final but lost 1-0 in the final to Robert Taylor's Dereham on 19th April 2006.

Paul left Norwich United during 2006 and took up coaching at Diss Town until January 2007 when he quit due to pressures of work commitments. Following Richard Carter's resignation from the Diss manager's position in March 2007, Paul and colleague Lyndon Rollingson took over as caretaker managers. He has since been replaced by Paul Tong.