Reilly was not interested in rugby league as a child and only watched a few Huddersfield matches until a friend at school encouraged him to play for a local amateur side. Paul started playing for Moldgreen Under-14s and discovered a real talent for the game. He was playing well at Moldgreen and as a result he attended trials at Halifax Blue Sox. They offered him a contract for 1997's Super League III, but as the 1996 season was only halfway through he was training at the Huddersfield Giants, after four or five weeks the then coach of the Huddersfield Giants, Darryl van der Velde had seen enough and offered him a deal. In 2001, he spent a month on loan at Batley Bulldogs. Reilly established himself as the first choice at Huddersfield Giants, and he was a stand-out player in both the successful 2002 Northern Ford Premiership campaign and then later in the Super League, where his passionate, whole-hearted performances were a key factor in the Huddersfield Giants establishing themselves as a competitive club. He played twice for England in the 2004 European Nations Cup, including a man of the match performance in the final against Ireland, in which he scored two tries in the first seventeen minutes. He featured for his home town team in the 2006 Challenge Cup Final, where he performed a memorable try-saving tackle on Ade Gardner to keep his side in the game in the first half. Towards the end of 2006 Reilly released a testimonial booklet entitled "The Life of Reilly" which celebrated his 10-years with the Huddersfield Giants and featured contributions from many past players and coaching staff. Reilly had a joint testimonial match with Keith Senior of the Leeds Rhinos at Headingley Rugby Stadium, Leeds on Friday 26 January 2007. Reilly announced at the start of 2007's Super League XII that he had signed a one-year extension to his contract and intended to retire at the end of the season after 11 years with his hometown club. He scored 8 tries in the season and helped to steer the Huddersfield Giants to a memorable 5th-placed finish in Super League. It was announced in August 2007 that the Huddersfield Giants would not be renewing Reilly's contract, respecting his wish to retire, and he was proudly carried off the field by team-mates following the club's 16-22 play-off defeat by Hull F.C. at the end of 2007's Super League XII. Despite intending to retire, Reilly was offered a lucrative contract by Wakefield Trinity Wildcats in September 2007 and signed for the club. However, after only four appearances it was revealed that he had sustained a serious neck injury and it seemed likely he would never play again. However, he overcame this injury and played for Oldham in the Co-operative Championship 1.
