[1] Born in Leicester,[1] Barnes completed an apprenticeship with Notts County before signing a professional contract in November 1985, making his debut in February 1986.

[3] He joined Stoke City on transfer deadline day in 1989–90, being one of a large number of players signed by Alan Ball in an attempt to avoid relegation.

Under Lou Macari in 1991–92 he found himself in the reserves due to the form of Wayne Biggins and Mark Stein.

[3] He played in 18 matches scoring four goals and was an unused substitute in the 1992 Football League Trophy final.

[3] York City manager John Ward spotted Barnes in Stoke's reserves and signed him in July 1992.