שטפן רויטר התחיל את קריירת הבוגרים בנירנברג בעונת 1984/85, כאשר הקבוצה שיחקה בבונדסליגה השנייה. בעונת הבכורה שלו בקבוצה, ערך רויטר 25 הופעות, הבקיע שלושה שערים, וסייע לקבוצה להעפיל לבונדסליגה מהמקום הראשון. בשלוש העונות הבאות, רויטר הפך לשחקן הרכב קבוע בנירנברג, והחמיץ שני משחקי ליגה בלבד בשלוש עונות. בעונת החזרה של נירנברג לבונדסליגה, 1985/86, הבקיע רויטר שני שערים, ונירנברג סיימה במקום ה-12. בעונת 1986/87 הבקיע רויטר שישה שערים ונירנברג סיימה תשיעית. בעונתו האחרונה של רויטר בנירנברג, 1987/88, הבקיע רויטר שני שערים, ונירנברג סיימה עונה מוצלחת במיוחד במקום החמישי, כשרויטר משתף פעולה עם יורן אנדרסן, דיטר אקשטיין ומנפרד שוואבל. לאחר עונה זו רויטר זכה להתעניינות של מועדונים גדולים, ועזב את נירנברג, בה ערך 125 הופעות וכבש 13 שערים.