On July 3rd 2002, Darlington left back Paul Heckingbottom joined Norwich on a three year contract to act primarily cover for Adam Drury at left back. Paul was signed rather than Norwich's initial target Andy Dawson (Scunthorpe) as Paul was available on a Bosman free transfer whilst Dawson would cost approximately £100,000 which would be too much for the cash-strapped Canaries. Paul's signature on a contract from Norwich ended a number of month's speculation that also suggested Burnley were keen on the former Manchester United trainee.

Born in Barnsley in July 1977, Paul began his career at Old Trafford as a trainee before joining Sunderland for the 1995/6 season. In his next four season with the Black Cats, he did not break into the first team but had loan periods at Scarborough (1997/98 - 29 appearances) and Hartlepool (1998/99 - 5 appearances, 1 goal). He joined Darlington initially on loan (10 appearances in 1998/99) before signing for them for the 1999/2000 season where he made 45 appearances scoring once. Another 18 appearances and a third league goal came in the 2000/01 season. In between these spells with Darlington, he had a trial with Bolton in March 1999.

On 8th April 2003, Norwich announced that they would be giving Paul a free transfer, and that his name would be circulated to league and conference clubs. The latter part of June 2003 saw media suggestion that Bradford would make a move to take Paul to the Valley Parade. This materialised on 3rd July 2003 when Paul signed a two year deal with the Bantams despite interest from Colchester, Southend and Doncaster. Bradford announced the signing of striker Michael Branch from Wolves at the same time. A return to his native Yorkshire and a chance to continue playing in Division One appealed to Paul. In return, Bradford expressed that Paul was the leftback they had been looking for - however despite his efforts, the Bantams were relegated to Division Two in April 2004.

Bradford's dire financial situation may put the club out of business and so all the players were encouraged to find new homes. According to the People on May 16th 2004, Sheffield Wednesday were keen to bring Heckingbottom to Hillsborough. This move came true on Tuesday 25th May 2004 with Paul signing a two year contract with the Owls, stating publicly that he was excited by Chris Turner's vision for taking Wednesday forward.

On 13th January 2006, Paul was loaned to Barnsley and was made a permanent transfer the following week. Paul played 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 won on penalties with Paul scoring one of their goals

Paul returned to Bradford on 16th July 2007 signing on a loan deal until 1st January 2008. After 23 games on loan for the Bantams, Paul turned this into a permanent transfer on 8th January 2008. He made a further 30 appearances for Bradford with his final months at Valley Parade hindered by a tendonitis injury.

Paul signed for Conference side Mansfield on 2nd June 2009. Mansfield manager David Holdsworth said: "Paul's a class act, an accomplished player. He's played at a high level and we're lucky to get him."

Paul departed Conference side Mansfield Town on loan to rivals Gateshead during the January 2010 transfer window. However the experienced left-back would miss Gateshead's first fixture since his signing as they were due to play Mansfield and a condition of the loan was that he could not play against his former club

Heckingbottom was one of eight players released by Mansfield at the end of the 2009/10 season. In May 2010, he rejoined Gateshead

He returned to Yorkshire in the summer of 2011, signing for Harrogate Town.

On 29th May 2012, he was appointed as Director of Pontefract Colleries' Academy side for 16-18 year olds, working closely with Colls’ first team manager Brendon Ormsby. He then joined Barnsley as a development coach. On 4th December 2013, he was appointed as caretaker assistant manager following the sacking of manager David Flitcroft who was replaced by Assistant Manager Micky Mellon.

When Barnsley sacked manager Danny Wilson on 12th February 2015, academy coaches Mark Burton and Paul Heckingbottom were placed in caretaker charge. When the new manager Lee Johnson left Barnsley in February 2016, he became caretaker manager again and led them to a Johnstone's Paints trophy win and a League One play-off finals victory over Millwall on 29th May 2016 which saw the Tykes promoted to the Championship. They finished 14th in the Championship in 2016/17.

Heckingbottom was linked with the vacant manager's position at Sunderland in mid-November 2017.

Three days after he signed a new rolling contract with Barnsley, Heckingbottom joined Leeds as their new manager on 6th February 2018 following the departure of Thomas Christiansen. The 40-year-old has agreed a deal until the end of 2018-19. Leeds, who dismissed 44-year-old Dane Christiansen after just eight months and had not won since Boxing Day 2017. Heckingbottom became Leeds' ninth different first-team boss since 2014. BBC Radio Leeds reports the Whites paid £500,000 to activate a release clause in Heckingbottom's Barnsley contract

Leeds finished 13th. He was sacked by Leeds on 1st June 2018 after 16 games in charge and replaced by Marcelo Bielsa.

On 13th February 2019, he was named as the new manager of Scottish side Hibernian replacing Neil Lennon who left in January. Heckingbottom signed a three-and-a-half-year contract and will be assisted by former Scotland international Robbie Stockdale. Hibs finished in fifth position, but Heckingbottom was unhappy that the team "downed tools" in the last few matches of the season.

Hibs only won one of their first 11 league matches in the 2019/20 season and Heckingbottom was sacked by Hibs on 4th November 2019 following a 5–2 defeat by Celtic in the League Cup with Hibs sitting 10th place in the league. He was replaced by former Sunderland boss Jack Ross. 

He joined Sheffield United in July 2020 as Under-23s Manager. On 13th March 2021 he was promoted to caretaker manager following the dismissal of Chris Wilder. He will be assisted by ex-Bournemouth manager Jason Tindall, with Alan Knill also staying on coaching staff. Unfortunately Heckingbottom couldn't save the Blades who were relegated from the Premier League on 17th April following a loss to Wolves. He was replaced by former Watford and Fulham boss Slavisa Jokanovic. Heckingbottom returned to managing the Under-23s.

On 25th November 2021 Heckingbottom was appointed as Blades' manager on a four and a half year deal replacing Jokanovic who had been sacked after winning just six of his 19 leagues games in charge. This left United eight points off the Championship play-off places. Heckingbottom will be assisted by former Sheffield United player and coach Stuart McCall, who leaves Blackpool. Former Blades striker Jack Lester has been appointed head of player development. Chairman Yusuf Giansiracusa said: "We look forward to embarking on a new era in Blades football with Paul at the helm.Paul possesses the personal leadership qualities and technical football skills the board feels are essential to successfully implement the board's strategic directives." In his first season they secured fifth place but were knocked out in the play-off semi-finals by Nottingham Forest.

Heckingbottom led the Blades to promotion to the Premier League, securing promotion on 26th April 2023 with a 2-0 win over West Brom that secured United's second place behind Burnley.

On 5th December 2023 Heckingbottom was sacked by Sheffield United with the club at the bottom of the Premier League with five points after losing 11 of their opening 14 games. They lost 5-0 to Burnley on 2nd December 2023. Heckingbottom was replaced by Chris Wilder. Stuart McCall also left the club