One of the products of the Dundee United's highly efficient scouting and coaching network in the west of Scotland, Glasgow-born McKinlay was signed from Hamilton Thistle in 1986. He won a place in the 1988 Scottish Cup Final side at the age of 19, despite previously having made just 12 League appearances.
An energetic and perceptive midfielder, he took some time to claim a regular first-team place, but when he did was a most effective link man. He suffered a major disappointment in May 1994 when a caution for an innocuous tackle in a League match carried him over the points threshold and led to him being suspended when United achieved their historic first Scottish Cup triumph. He took rather longer than might have been expected to become a full international, but went on to win 14 caps while at Tannadice, the latter two as a First Division player. He is one of only three players from that division to play at full international level for Scotland since League reconstruction in 1975.
Following United's relegation he asked for a transfer and got his wish when Blackburn Rovers paid £1.75 million for him in October 1995. He came close to joining boyhood heroes Celtic Fc when then manager Tommy Burns made a last-ditch attempt to sign him from under the noses of Blackburn Rovers. McKinlay had brief spells with Bradford City and Clydebank before joining Premiership side Leicester City in 2002, where he scored once against Coventry City. In 2004, Chris Coleman signed him to help bolster Fulham's reserve squad.
McKinlay won a total of 29 Scotlandcaps, 14 while with Dundee United.
On 21 December 2007, Fulham first-team coach Ray Lewington and reserve team manager McKinlay took over after manager Lawrie Sanchez was sacked. Roy Hodgson was appointed nine days later. He has been a coach at Fulham, working with the reserve side and developing youth talent. Later become Northern Ireland assistant manager, but returned to Fulham to manage the side's 4–0 defeat at Everton, on 28 April 2012 due to Martin Jol's chest infection and was again in charge on Merseyside, for Fulham's historic win against Liverpool.