Schuster, who lived his youth in the East Germany, was one of the first East German players to make the move into the West, starting in Eintracht Braunschweig and soon moving on to Karlsruher SC in 1991, where he established himself as a respected center-back.
A move to 1. FC Köln in 1997 proved less successful, and in the following journeyman years he played in Turkey and Austria. He then played for newly promoted Second Bundesliga club LR Ahlen in 2000, where he has a good stint, before he returned to Austria and then played in the Oberliga, the fourth-highest league with Waldhof.
On 30 May 2009 he was named as the new head coach of the Stuttgarter Kickers, where he signed a two-year contract until 30 June 2011, which was prematurely extended on 1 April 2010 until 20 June 2012. He guided Kickers to the Regionalliga Süd title in 2011–12, and promotion to the 3. Liga, but was sacked in November 2012 after going five games without scoring a goal. He was appointed manager of 3. liga side SV Darmstadt 98 a month later.
Despite Schuster helping Darmstadt 98 off the bottom of the league, they finished among the relegation places in the 2012–13 season, Schuster's Darmstadt avoided dropping into Germany's fourth tier, the Regionalliga Südwest, thanks to the failure of fierce local rival Kickers Offenbach in obtaining the licence for the new season due to going into administration.
In the following season, to the surprise of all experts, Darmstadt managed to get third in the league which meant a relegation-promotion play-off spot for the 2. Bundesliga. Darmstadt faced Arminia Bielefeld in the play-off and won promotion in dramatic fashion after losing 1-3 at home in the first leg but turning the deficit around in the second leg and scoring the winning 4-2 in the 122nd minute which meant promotion on away goals.
In the following season Schuster managed to surprise everyone for a second time by finishing 2nd in the league and achieving back-to-back promotion to the Bundesliga after a 33-year absence.