Robertson began playing football with Deeside Boy's Club (now Banks O' Dee FC) before he started his football career by signing an "s" form with local club Aberdeen in 1986, where he won a Scottish League Cup winners medal against Rangers in 1989 and a Scottish Cup winners medal in 1990 against Celtic in a match which led to a thrilling 9–8 penalty shoot out, Robertson being one of the scorers in the shoot out.
Robertson moved to Rangers for £970,000 in 1991. With Rangers, he helped the club to a record nine championship titles in a row. During his time at the club, he won three caps for Scotland. Robertson signed for Leeds United in 1997 for £500,000, but recurring injury problems curtailed his spell in England and he played only 26 league matches in four years at Elland Road.
Robertson retired from football in 2001 but was back playing in 2002 when he was appointed player/assistant manager of Scottish Football League club Montrose. He scored his first and only goal for Montrose in a 3-2 defeat at Cowdenbeath in the Scottish League Cup. His playing career with Montrose was cut short, however, due to one of his Achilles tendons snapping during a match against Greenock Morton in the same year.
Robertson had a brief spell managing Elgin City. In September 2006, Robertson was appointed manager of Montrose but he resigned just four months later. He now resides in Phoenix, Arizona, where he is Director of Boy's Coaching at Sereno Soccer Club. Robertson was Head Coach of Phoenix FC of the USL Pro League. in 2013.