Stone was born in Gateshead. began his career at Nottingham Forest, where, despite suffering three broken legs, he managed to establish himself as a vital team player, and also earned a call up to the England squad, making his international debut in 1995 against Norway. He went on to earn nine caps, scoring twice, and was part of Terry Venables' squad for UEFA Euro 1996. However, another serious leg injury meant he missed the entire 1996–97 season that saw Forest relegated in last place. The following season he made his way back into the Forest team and was part of their successful bid for promotion in 1997-98. The following season, with Forest struggling against relegation from the Premier League, he moved to Aston Villa for £5.5 million in March 1999, after having made 229 appearances for Forest. He soon became a vital team player under then manager John Gregory, and came on as a substitute in the 2000 FA Cup Final at Wembley Stadium. However, following Gregory's dismissal, Stone failed to impress new manager Graham Taylor, and, having failed to land a place at Manchester United two seasons earlier, he was transferred to Portsmouth for the 2002–03 season, having played in 121 games for Villa. Despite continued injuries, he established himself as a regular in the Portsmouth team. He was an invaluable part of the team that won promotion to the Premier League in 2002–03, and then achieved a mid-table finish the following season and narrowly avoided relegation the next. However, when his contract expired in June 2005, new manager Alain Perrin decided to release Stone, and he signed for Leeds United. Stone's career at Leeds was short-lived. He was injured in training as soon as he joined the club, and it took him most of his first season to recover from the tendinitis in his Achilles tendon due to contracting MRSA after the operation and then having to have a further two operations for the MRSA. Stone played a few matches at the end of the 2005–06 campaign, and continued to play at the start of the 2006–07 campaign, scoring once against West Brom. Injuries, however, struck again, and Stone retired early on 15 December.
International career
Stone was capped nine times at senior level for England. He made his debut in October 1995, coming on as a substitute in a 0–0 draw against Norway. Four days later, again coming off the bench, Stone scored his first international goal in a 3–1 win over Switzerland at Wembley Stadium. He also scored in his next game, which was his first start, as England drew 1–1 with Portugal. Stone was capped three more times in the build-up to UEFA Euro 1996, where he was selected by manager Terry Venables as part of the 22-man England squad. He made three appearances during the competition, all off the bench. Stone's introduction during extra-time of the quarter-final versus Spain was his last appearance for England.
Coaching career
On 27 July 2010, he was appointed reserve team assistant manager to Peter Beardsley at Newcastle United after a successful time working at their academy. Stone was promoted to first team coach on 14 December 2010, by new manager Alan Pardew. Stone remained as first team coach after Pardew resigned to join Crystal Palace, with John Carver put in charge of Newcastle until the end of the season. On 9 June 2015, both he and Carver had their contracts terminated by Newcastle ahead of the announcement of Steve McClaren as new head coach. On 12 November 2018, he replaced Michael Duff as the new U23 manager of Burnley.