In August 1997, with Still now in charge of Barnet, Heald put pen to paper to sign for the club; the transfer fee of £130,000 is still a club record. He made his Bees debut at his former club Norwich City in the League Cup on 12 August 1997. Barnet lost the game 2-1 but won the return at Underhill winning 3–1 on the night coming from a goal down at half time. Heald made 50 appearances and scored five goals helping the team to a seventh-place finish in Division Three. The club also reached the play-offs, losing to Colchester United. Missing the first half of the following season due to an ankle and then a back injury making only 19 first team appearances, Heald returned to the side in early 1999 at home to Shrewsbury Town. The Bees finished 16th in the league but found their feet again the following season with another play-off semi final against his old club Peterborough United, but lost on aggregate 5–1. Heald had featured in 46 games scoring five times. The 2000–01 season saw Barnet relegated back to the Football Conference. Heald made 45 appearances that season again scoring five times. In 2001-2 Barnet finished 5th in their first season back in the Conference, Heald featuring 44 times scoring twice. In April 2002, he was selected for the England non-league international side to play the Netherlands. In his final season at Underhill the club finished 11th in the Conference. On 27 March 2003, after making a further 18 appearances scoring 4 times Barnet sold Heald and teammate Wayne Purser to Leyton Orient for a joint fee of £18,000.
Heald was unable to secure a regular first team place at Orient, and in March 2004 he was released from his contract to join Rochdale. After a year at Spotland he briefly joined York City, then Burton Albion but soon moved on again to Ashton United in the Northern Premier League.
Moving back south Heald joined Aldershot Town for a season before he started to study for a degree in sports science and prepare for life after football as a teacher. To support this he had a spell as a fire officer while turning out part-time for Thurrock before a year later accepting the position of youth team coach at Wycombe Wanderers. Entering full-time teaching at The Latymer School in Enfield he briefly joined Enfield Town at the age of 37.
