McKinnon was born in Dundee on 5 August 1970. He started his career with Dundee United, turning professional on 12 August 1986. He soon gained attention as one of the most promising young midfielders in Scottish football. He impressed Brian Clough enough to win a £750,000 move to Nottingham Forest in July 1992, but almost as quickly as he had arrived found himself out of first team contention, Clough deciding that his skilful passing was not what he wanted for his midfield. He left to join Aberdeen on 8 February 1994, costing the Dons £300,000.