Born in Birmingham, Yates began his footballing career as a trainee at hometown club Birmingham City, before going on to sign professional terms with the club in 1988. He spent a total of three seasons at St Andrew's, making 66 first team appearances, including one in the side that won the 1991 Football League Trophy.
In 1991 Yates was sold to Burnley for £40,000 but struggled to hold down a regular position. Spells at Lincoln City and Doncaster Rovers followed, before Yates dropped out of the Football League to sign for Conference side Kidderminster Harriers in 1994, going on to become club captain. In his first season at the club Kidderminster reached the final of the FA Trophy, losing 2–1 to Woking. In 1997 Yates seemed set for a return to League football as Kidderminster led the Conference by a significant margin going into the final months of the season. However, the Harriers let the lead slip, allowing Macclesfield Town to overtake them and claim the championship.
In January 1999 Yates left Kidderminster to join local rivals Cheltenham Town for a fee of £25,000, helping the Robins to secure the league title and a place in the Football League. Yates remained with the Gloucestershire outfit until February 2004, enjoying reasonable success, the highlight being a victory in the 2002 Third Divisionplay-off final. After falling out of favour at Whaddon Road, in 2004 Yates returned to Kidderminster, by this time a Football League club themselves, playing his part in the club's successful fight against relegation.
At the end of this season Yates called time on his playing career, becoming first team coach at Burnley alongside the manager who had signed him at Cheltenham, Steve Cotterill. Following a year and a half in that role, Yates was offered the chance to take up his first managerial position by former club Kidderminster, now back in the Conference, a position which he took up in January 2006. In his first season in charge he steered the club to safety from relegation, and in the second secured a top-half finish as well as an FA Trophy Final place at the new Wembley Stadium. He was twice voted Manager of the Month in this second season, for the months of December 2006 and January 2007.
He was appointed manager of League Two team Cheltenham on 22 December 2009, with Neil Howarth joining him as first team coach. He led them to the 2012 League Two play-off final which they lost 2–0 to Crewe Alexandra. Yates guided Cheltenham to the League Two playoffs again in 2013 only to lose to Northampton Town 2-0 on aggregate.