Schulden, die AJA zu Beginn der Trainerkarierre Rouxs drückten, waren durch die zahlreichen Aufstiege rasch abgetragen worden- war aber denoch nicht auf Rosen gebetet:
Auxerre lag in der tiefsten Provinz, die Gegend hatte eine schwache Infrastrukur, und das Stadion war klein. So musste der Verein sehr kreativ sein, um das Budget zu stemmen. Während der Winter- und Sommerpausen ließ man beispielsweise den Rasen wachsen, um ihn dann vor Saisonstart an die Bauern zu verkaufen. Die dadurch generierten Einnahmen waren natürlich nur Peanuts.
Die Haupteinnahmequelle war die hervorragende Jugendarbeit aus der zahlreiche Spieler hervorgingen, die das Team aus Auxerre bereicherten, oder die teuer verkauft wurden.Aber damit dies auch so blieb, benötigte man Scouts, um die Talente zu entdecken, bevor andere, größere Klubs auf sie aufmerksam wurden. Doch Scouts waren teuer, viele konnte Auxerre nicht beschäftigen. Aber der findige Guy Roux fand auch für dieses Problem eine Lösung: Er wies seinen Trainerstab an, während ihres Urlaubes an ihrem Urlaubsorten die Spiele des nächsten Fußballklubs zu besuchen.
Mit diesen ungwöhnlichen, aber erfolgreichen Maßnahmen, gelang es Guy Roux seinen AJ Auxerre in der zweiten Liga zu etablieren, und sogar noch mehr als das:
5 Jahre nach dem Aufstieg, 1979, stürmte das Team aus der tiefsten Provinz bis ins Finale der Coupe del Nationale.
Mit den Einnahmen aus dem Pokal konnte man endlich ein Jugendinternat erichten, dass die Jugendarbeit von Auxerre weiter aufwertete, und Auxerre für Jugendspieler endgültig zu einer der besten Adressen im französischen Fußball machte.

1. Liga & Europa

In der Saison 79/80, ein Jahr nach dem Pokalfinale, stieg das Team von Guy Roux ( u.a. mit Eric Cantona, Basile Boli, Jean Marc Ferreri...) in die 1 Division, die heutige Ligue 1 auf.
Die Euphorie in der Stadt war grenzenlos. erst recht als Präsident Hamel nach der Aufstiegsfeier bekannt gab, dass Guy Roux zusätzlich zum Trainerposten auch das Amt des Sportdirektors ausfüllen würde.
Und der rasante Aufstieg des kleinen Dorfklubs ging weiter.
Erst gelang der problemlose Klassenerhalt, als Zehnter, zwei Jahre später Dritter und erreichte das internationale Geschäft. Spätestens jetzt schien das Märchen von Auxerre etwas surreal. Völlig unrealistisch- nur das es eben doch real ist...
Das erste Europapokalspiel überhaupt bestritt AJA gegen Sporting Portugal.
Auch wenn man mit 3:2 n V. den Kürzeren zog, entäuscht war kaum jemand.
Zumal man sich dieser Saison erneut für Europa qualifizierte, als 4 der Divison 1. In den nächsten Jahren etablierte sich das Team aus der kleinen Stadt aus der Yonne im oberen Tabellendrittel.
In der Saison 92/93 gelang es dem Team erneut sich für den Europapokal zu qualifizieren, trotz des Verlustes wertvoller Spieler wie Cantona, Ferreri oder Darras. Und in der darauffolgenden Saison konnten die Fans auch endlich ihren ersten Euro-Cup-Sieg ihres Teams feiern, Auxerre kam bis ins Viertelfinale, wo sie Borussia Dortmund knapp unterlagen.
Diese Saison läutete die erfolgreichste Zeit des AJ Auxerre ein:
'94 holte man mit dem Coupe de France den ersten Titel, und im Jahre '96 gelang das Double aus Landespokal und Meisterschaft. Dazu ereichte man das Viertelfinale der Championsleague. Aus diesem Jahr datiert auch der höchste Sieg der Klub-Historie, ein 7:0 gegen Olympique Lyon.
Im der Saison 98/99 gewann der Klub zudem den Ui-Cup.
Auch die Jugendmannschaften waren in diesem Zeitraum sehr erfolgreich, bis 1999 holten sie 5 Mal den Coupe Gambardella, den A-Jugendpokal Frankreichs, und zementierten damit den Ruf des AJ Auxerre als beste Talentschmiede des Landes.