Spartak Moskau

Mostowoi spielte sich in das Blickfeld von Spartak Moskau, die ihn 1986 im Alter von 18 Jahren unter Vertrag nahmen. Spartak war der Verein der gewerkschaftlich organisierten Sportbewegung und zählte zu den bekanntesten und erfolgreichsten Fußballmannschaften der Sowjetunion. Von Trainer Konstantin Beskow wurde Mostowoi am 7. Juni 1987 gegen Kairat Alma-Ata (2:1) erstmals in einer Partie der höchsten Spielklasse (Wysschaja Liga) eingesetzt. Neben den Vereinsgrößen Fjodor Tscherenkow und Sergei Rodionow etablierte sich Mostowoi allmählich als Stammspieler und erzielte schon vier Wochen nach dem Debüt seinen Premierentreffer gegen Schachtar Donezk (3:0). Mit Spartak gewann er 1987 und 1989 die sowjetische Meisterschaft. Nachdem sein alter Förderer Romanzew den Trainerposten übernommen hatte, gelang Mostowoi der endgültige sportliche Durchbruch. In der letzten Saison der Sowjet-Liga (1991) war der Edeltechniker viertbester Torschütze (13 Tore), allerdings hatte die Mannschaft im Titelkampf das Nachsehen und wurde nur Vizemeister. Im Europapokal der Landesmeister erreichte Spartak nach Siegen über renommierte Gegner wie die SSC Neapel und Real Madrid das Halbfinale, scheiterte dort jedoch an Olympique Marseille.

Portugal und Frankreich

Nach dem Zerfall der Sowjetunion stand den osteuropäischen Staatsamateuren der Weg in den finanziell lukrativen Westen offen und im Januar 1992 wechselte Mostowoi zum portugiesischen Rekordmeister Benfica Lissabon. Dort standen mit Sergei Yuran und Wassili Kulkow bereits zwei sowjetische Spieler im Kader. Allerdings fiel Mostowoi die Anpassung schwer und er konnte sportlich nicht überzeugen. Der Neuzugang kam nie über die Rolle als Ergänzungsspieler hinaus und konnte sich auf seiner Position nicht gegen Rui Costa und Paulo Futre durchsetzen. Im Pokalfinale 1993 (5:2-Sieg über Boavista Porto) kam er nicht zum Einsatz.

Mostowoi geriet schließlich vollends auf das Abstellgleis, weshalb er sich im Dezember 1993 an den französischen Klub SM Caen ausleihen ließ. In der Rückrunde 1993/94 zeigte der Neuzugang eine aufsteigende Form (15 Einsätze, 3 Tore) und half mit, Caen vor dem drohenden Abstieg zu bewahren. Gegen den amtierenden Meister Olympique Marseille erzielte Mostowoi am 34. Spieltag den wichtigen 1:0-Siegtreffer.

Nach einem halben Jahr zog Mostowoi weiter und folgte seinem Trainer Daniel Jeandupeux innerhalb der Division 1 zu Racing Strasbourg, die ihn am 19. August 1994 fest verpflichteten. In den kommenden beiden Spielzeiten (1994/95, 1995/96) war Mostowoi als Spielmacher einer der wichtigsten Spieler des Kaders. 1995 unterlag Racing im Finale der Coupe de France mit 0:1 gegen Paris Saint-Germain. Allerdings qualifizierten sich die Elsässer kurz darauf durch den Erfolg im UI-Cup für den UEFA-Pokal. Obwohl Mostowoi nur zwei Jahre für Strasbourg aktiv war (23 Tore in 82 Pflichtspielen), wählten ihn die Fans in einer Umfrage zum Spieler des Jahrhunderts.

Celta Vigo

Im Juli 1996 wechselte Mostowoi zu Celta Vigo, einem Provinzklub aus dem unteren Mittelfeld der spanischen Primera División. Die Ablösesumme lag bei 325 Millionen Pesetas (etwa 1,9 Millionen Euro). Mit den Galiciern kämpfte Mostowoi in seiner Premierensaison 1996/97 gegen den Abstieg und musste bis zum 23. Spieltag auf sein erstes Tor warten, das ihm ausgerechnet im Derby gegen Deportivo La Coruña (2:2) gelang. Die anschließende Spielzeit 1997/98 beendete Celta überraschend als Tabellensechster und konnte sich erstmals seit 27 Jahren wieder für den Europapokal qualifizieren - der Startschuss zur bislang erfolgreichsten Phase der Klubgeschichte. Beim 2:1-Heimsieg über Real Madrid am 33. Spieltag hatte Mostowoi beide Treffer erzielt und seine Bedeutung für die Mannschaft untermauert. Neben seinem Landsmann Valeri Karpin, mit dem er bereits bei Spartak Moskau zusammengespielt hatte, war er mittlerweile der entscheidende Dreh- und Angelpunkt des Offensivspiels. Sein kreatives Spiel und die wichtigen Tore, die er für Celta Vigo schoss, machten ihn zur Kultfigur des Vereins, was ihm den Spitznamen Zar von Balaídos einbrachte. 2000 feierte er mit Celta Vigo den Gewinn des UEFA Intertoto Cup. Den Abstieg von Celta Vigo, in der Saison 2003/04, in die Segunda División konnte Mostowoi nicht verhindern. Er wechselte für die zweite Hälfte der Saison 2004/05 zu Deportivo Alavés, bevor er dort seine Karriere beendete.

Deportivo Alavès

Nachdem Mostowoi acht Monate verletzt und schon 36 Jahre alt war, konnte er bei Alavés nicht mehr richtig Fuß fassen und seine gewohnten Stärken ausspielen. Er spielte nur ein einziges Spiel gegen den FC Cádiz, wo er in der 78. Spielminute eingewechselt wurde und das einzige Tor bei der 1:3-Niederlage für Alavés schoss. Nach nur 30 Tagen im Verein, bat er die Vereinsführung seinen Vertrag aufzulösen, da er an starken Rückenprobleme litt.