Paul Hayes is the younger brother of former Arsenal and Celtic forward Martin Hayes, Paul is described as natural goalscorer with happy knack of being in the right place at the right time. He hails from Essex and was with Norwich since the age of 13. He had an excellent pre-season in the summer of 2001 scoring five at Wroxham, one at Colchester and one at Carrow Road against Premiership giants Arsenal. Sammy Morgan however said the youngster still had work to do: "Hayes is a good goalscorer, he has good movement and a good touch. I, as an ex centre-forward, continually question him about his bravery. He's got lots of technical quality but I am demanding more from him in terms of getting into the box and being a brave number nine with a good work ethic. If he does that he's got a chance because he's got the technical quality."

Despite sitting on the bench for the final two league games of 2001/02 (vs Barnsley and Stockport) and participating in pre-season friendlies, Paul became frustrated at his lack of first team opportunities, Paul agreed to join Torquay United on 22nd October 2002 on a week's trial. Nigel Worthington intended for him to "toughen up" both physically in Division Three and mentally, by playing for a club whose premises and infrastructure was less developed than at Carrow Road. "We've sent him to Torquay to show him the other side of life and to get him roughed up a bit," said Worthington. "He's a big, strong centre-forward, he's a little bit soft so he can go and experience the delights of lower league football and maybe he'll come back and appreciate the surroundings and the quality that he has here." Worthington confirmed Hayes was not on a loan deal but would be in consultation with the Gulls over whether it would be possible for the 19-year-old to play a competitive match for them.

On 3rd December 2002, Norwich released Paul from his Academy contract as his opportunites at Carrow Road would be limited. He had also been trialling with Scunthorpe and his contract was passed to them. This was recorded as a free transfer although a substantial sell-on clause had been included.

He scored on his debut for Scunthorpe against Southend after coming on as substitute. After scoring a wonder goal against Hull on his full debut and then scoring two goals for Scunthorpe against Rochdale on March 19th 2003, Scunthorpe decided to offer Paul a new deal as a full-time professional rather than as a youth team player.

At Christmas 2004, he was the second-leading scorer in League Two and as such had gained the interest of Championship sides Brighton, Derby, Nottingham Forest and Sheffield United. Barnsley manager Andy Ritchie was also said to have watched him in May 2005 with Hayes mulling over a new three year contract offer from promoted Scunthorpe. Paul eventually signed for Barnsley on 2nd June 2005.

Paul scored for Barnsley in their League One play-off final against Swansea at the Millennium Stadium on 27th May 2006, which finished 2-2 but which the Tykes, also featuring Paul Heckingbottom, won on penalties with the two Pauls both scoring penalties. Swansea did not field either Darren Way or Adrian Forbes.

Although Hayes has started 26 games for Barnsley during 2006/7, scoring five times, he had slipped down the Oakwell pecking order following Istvan Ferenczi's arrival. He was therefore allowed to join Huddersfield on loan on 23rd February 2007 with view to a permanent move in the summer.

Paul returned to Scunthorpe in June 2007 on a three-year deal with the fee set to be decided by a tribunal. Unfortunately Hayes couldn't help Scunthorpe avoid relegation to League One in 2007/8