W 1988 roku Andreas przeszedł FC Schalke 04, grającego wówczas w drugiej lidze. W nowym zespole po raz pierwszy wystąpił 23 lipca w zremisowanym 1:1 domowym meczu z Fortuną Düsseldorf. Na koniec sezonu 1990/1991 roku wywalczył z tym klubem awans do 1. Bundesligi i tam od 1992 roku był podstawowym zawodnikiem klubu. W 1996 roku zajął z Schalke 3. pozycję w tabeli. W sezonie 1996/1997 wystąpił w Pucharze UEFA i dotarł z Schalke do finału tych rozgrywek. W nim klub z Gelsenkirchen najpierw pokonał 1:0 Inter Mediolan, jednak w rewanżu przegrał w takim samym stosunku. Doszło wówczas do serii rzutów karnych, Schalke zwyciężyło 4:1 i zdobyło swój pierwszy w historii europejski puchar. Eigenrauch rozegrał obydwa finałowe spotkania w pełnym wymiarze czasowym. W sezonie 1999/2000 Müller pełnił rolę rezerwowego w „Die Knappen” i wystąpił tylko w 6 spotkaniach. Latem 2000 zakończył piłkarską karierę, a w Schalke 04 rozegrał 286 meczów, w których strzelił 30 bramek.
Od 17 maja 2006 do 9 marca 2009 Müller pełnił funkcję menedżera w Schalke 04.