Born in Glasgow, Stark made his professional debut in 1975 in nearby Paisley for St Mirren. Two years later he won his first honour, a First Division winners medal. After 255 games for St Mirren, scoring 60 goals, he was signed by Aberdeen for £80,000. During a period of success for the side, he helped Aberdeen to win a European Super Cup in 1983, a Premier Division and Scottish Cup double in 1984, another league title the following year and a League Cup and Scottish Cup double in 1986.
Stark was signed by Celtic in 1987, for a £100,000 transfer fee. In three seasons with the club he won two further Scottish Cups and a League Championship, before leaving for Kilmarnock for two seasons. In 1992, he transferred to Hamilton Academical as a player/coach, but returned to Kilmarnock the following year under manager and former Celtic colleague Tommy Burns. Stark retired from playing in 1994, having scored over 100 league goals.
After retiring as a player, Stark became assistant to Tommy Burns at Celtic. When Burns left Celtic in 1997, Stark managed the side for three matches in a caretaker capacity before leaving himself. Stark then had spells managing Greenock Morton and St Johnstone before becoming Queen's Park manager in 2004.
Stark led Queen's to one of their greatest results of modern times in August 2006 at Firhill Stadium, when Queen's Park beat his former club Aberdeen on penalty kicks after a 0-0 draw in the 2006–07 Scottish League Cup. Stark also led the Glasgow club to promotion from the Scottish Third Division and later hailed the achievement as the highlight of his football career.
Stark left Queen's Park on 1 January 2008 to oversee the Scottish national youth teams, a role that involved managing the Scotland national under-21 football team. Stark's under-21 side reached the qualification playoffs for the 2011 UEFA European Under-21 Football Championship, but they lost out to Iceland. David Goodwillie, Danny Wilson and Barry Bannan were promoted from the under-21s to the full national team selected by Craig Levein in November 2010. The team finished in second place in their qualifying group for the 2013 UEFA European Under-21 Football Championship, but did not gather enough points to be eligible for the playoffs.
Stark was placed in caretaker charge of the Scotland team for a friendly against Luxembourg in November 2012, following the departure of Craig Levein. He resigned from the position of Scotland under-21 manager in November 2014.
In June 2015, Stark was appointed assistant manager to Darren Young at newly promoted Scottish League One side Albion Rovers.
In June 2017, he was appointed manager at Scottish Lowland Football League side East Kilbride.Queen's Park
Scottish Third Division play-offs 2006–07