Schuster, who lived his youth in the DDR, 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.
Schusters first coaching job was as interim coach for ASV Durlach between October 16, 2006 and January 10, 2007. On May 30, 2009 he was named as the new head coach of the Stuttgarter Kickers, where he signed a two years contract until June 30, 2011, which was on April 1, 2010 prematurely extended until June 30, 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 five games without a goal. A month later he was appointed manager of third Bundesliga SV Darmstadt 98. Despite finishing among the relegation places in the 2012-13 season, Schuster's Darmstadt avoided dropping into Germany's fourth tier thanks to the failure of fierce local rival Kickers Offenbach to obtain a licence for the new third Bundesliga season.