Les années 1990 marquent le début de l'ère Joël Muller. Né le 2 janvier 1952 à Donchery dans les Ardennes, cet ancien joueur de Metz, Lyon, Nice et Dunkerque, a traversé la France avant de revenir poser ses valises au FC Metz, tout d'abord en tant que responsable du centre de formation, puis en tant qu'entraîneur. Fin tacticien, habile pédagogue, il prône des valeurs chères au club lorrain. Fidélité, rigueur, réalisme et combativité sur le terrain sont les maîtres-mots de sa conception du football. Perfectionniste, Joël Muller aime construire sur le long terme, insuffler ses valeurs aux jeunes du centre de formation afin ensuite de récolter les fruits de ce labeur collectif. Soucieux du moindre détail, exigeant envers les hommes comme envers lui-même, il est reconnu par ses pairs comme l'un des meilleurs entraîneurs de sa génération.

Ses quatre premières années à la tête du FC Metz ne sont pourtant pas flamboyantes. 12ème lors de la saison 1990-91, Metz effectue un bon parcours à domicile, ne subissant que deux défaites. Mais il ne décroche que quatre victoires en déplacement, malgré le présence d'Aloïcha Asanovic, le redoutable et fantasque meneur de jeu yougoslave, qui termine au 6ème rang des buteurs avec 13 réalisations à son actif. La saison suivante voit l'éclosion d'un attaquant opportuniste, adroit et puissant, François Calderaro, qui inscrit 19 buts et se hisse à la 2ème place du classement des buteurs. Il rejoindra ensuite le PSG d'Artur Jorge, mais n'aura que très peu d'occasions de s'y exprimer. Metz s'abonne à la 12ème place du Championnat, à laquelle l'équipe accède au terme des saisons 1991-92, 1992-93, et 1993-94, avec une différence de buts pratiquement identique à celles des saisons précédentes.

Il faut attendre 1994-95 pour que l'équipe messine prenne réellement son envol. Metz termine le Championnat à la 8ème place mais accède aux demi-finales de la Coupe de France. Après avoir battu Montpellier (2-1) lors des huitièmes de finale et Mulhouse (D2) lors des quarts de finale (2-0), l'équipe s'incline de justesse, sans avoir démérité, face au Racing Club de Strasbourg (0-1). Dès lors, les bons résultats vont s'enchaîner : Le FC Metz se classe 4ème à l'issue de la saison 1995-96, à 3 points du PSG, deuxième, et à 7 points du champion , l' AJ Auxerre qui réalise cette année là un beau doublé Coupe - Championnat.

L'équipe est solide et ne subit que 4 défaites à l'extérieur. En plus de cette honorable 4ème place, le FC Metz de Robert Pirès, Jocelyn Blanchard, Sylvain Kastendeuch et Patrick M'Boma, remporte sa seconde coupe de la Ligue. Après avoir écarté Lille et Niort (D2) sur le score de 2-0, Metz s'impose contre Guingamp (2-1) lors des demi-finales et affronte Lyon en finale, le 6 avril 1996 au Parc des Princes. Avec Pascal Olmeta dans les buts et Florian Maurice aux avants-postes, l'Olympique Lyonnais est donné favori. Paralysés par l'enjeu Metz et Lyon ne se libèrent pas et se livrent un duel sans saveur, même s'il n'est pas dépourvu de suspense. Les tirs au but départagent les deux finalistes. Les hommes de Joël Muller réussissent à transformer leurs tentatives. Le Lyonnais Marcello rate la sienne. 5-4 pour Metz, qui enrichit ainsi son palmarès.

La saison 1996-97 est celle des révélations ou de confirmation de valeurs montantes, à l'image de Robert Pirès, qui inscrit 11 buts, ou de Cyrille Pouget : les "P.P" flingueurs s'en donnent à coeur joie. Le FC Metz n'a jamais été aussi confiant, et la victoire obtenue à Marseille (2-1) au cours de la 3ème journée du Championnat est là pour le démontrer. Traoré et le météorite Bombarda offrent ce soir là 3 points à Metz. Le club termine à la 5ème place au classement, à une longueur du 4ème, Bordeaux, et deux du 3ème, Nantes. Réguliers et sans complexes lors des rendez-vous nationaux, sacrés régulièrement meilleure défense du Championnat, les hommes de Joël Muller sont cependant encore trop tendres lors des joutes européennes.

Ils tombent avec les honneurs en huitième de finale de la Coupe UEFA contre les Anglais de Newcastle United (1-1, O-2), au sein duquel évolue David Ginola et le colombien Asprilla. Le FC Metz peut toutefois s'enorgueillir d'avoir sorti le FC Tirol Innsbrück au premier tour (0-0, 1-0) grâce à un but du défenseur camerounais Rigobert Song, puis le Sporting Club du Portugal (2-0, 1-2) grâce à des buts de Amara Traoré, Didier Lang à l'aller et de Frédéric Arpinon au retour.