Born in Sheffield, South Yorkshire, Mills started his career with Sheffield Wednesday in 1982. He failed to earn a first team spot at Hillsborough, particularly following the "Owls" ascent to the First Division in 1983–84 under Howard Wilkinson's stewardship. He moved on to York City in June 1985. DenisSmith's "Minstermen" finished 7th in the Third Division in 1985–86, and Mills was voted Clubman of the Year. However a decline at Bootham Crescent saw the club slip to 20th in 1986–87, and Smith was replaced by Bobby Saxton. Mills was snapped up by John Rudge's Port Vale for £35,000 in December 1987. York went on to finish in the relegation places in 1987–88. Unable to fit him into the side due to the form of Ray Walker and others, Rudge converted Mills from a midfielder to a right-back. He made 19 Third Division appearances in 1987–88, scoring five goals. He played 55 games in 1988–89, playing in partnership first with fellow centre-backs Phil Sproson and Bob Hazell and later Gary West and Dean Glover, alongside full-backs Alan Webb and Darren Hughes, in front of goalkeeperMark Grew. This proved to be the most successful defence in the division, conceding just 48 goals in 46 league games. However a third-place finish meant that they had to overcome Bristol Rovers 2–1 over two legs in the play-off final, with Robbie Earle hitting both goals. Mills missed just one Second Division game in 1989–90, forming a formidable defensive partnership with Glover. He played 45 games in 1990–91, as Vale retained their second tier status. He played 40 games in the 1991–92 relegation season, scoring twice, and helped the club to win the TNT Tournamentin the summer. However, in autumn 1992 he developed knee trouble and underwent a series of unsuccessful operations, limiting him to just three league appearances in 1992–93. He was given a free transfer in May 1994. After retiring as a professional, he later attempted a comeback with Northern Premier League Premier Division sides Boston United and Matlock Town.
Style of play
Mills was a hard working player who played at both right-back and midfield. He was an excellent set-piece taker and part of Port Vale's "MBE" corner-kick routine: Mills to Darren Beckford to Robbie Earle. In May 2019, he was voted into the "Ultimate Port Vale XI" as a right-back by members of the OneValeFan supporter website.
Post-retirement
Mills became a drayman at a Sheffield brewery after leaving football.