La saison 1999/2000 s'annonce prometteuse, avec une participation en coupe Intertoto (élimination au dernier tour contre West Ham) et la venue sur les bords de la Moselle du jeune milieu de terrain de l'AS Nancy-Lorraine Christophe Bastien (plus gros transfert de l'histoire du club), du rennais Nicolas Goussé et de l'attaquant ukrainien Sergeï Skachenko. Malheureusement Christophe Bastien se blesse lourdement à une cheville et les deux attaquants peinent à confirmer tout le bien que l'on pense d'eux. Michele Padovano fait son apparition à la pointe de l'attaque quelques matchs, montre tout son talent, marque 4 buts, dont un magnifique coup-franc contre Marseille au stade Vélodrome, et se reblesse au tibia : on ne le reverra plus sous le maillot grenat. Cette saison est surtout marquée par un "drôle" de record : 17 matchs nuls en 34 matchs et meilleure défense…malheureusement c'est insuffisant dans un championnat où la victoire est à 3 points; les grenats terminent donc cet exercice à la 11ème place.

Pour la saison 2000/01 l'effectif est stable : les "cadres" sont épaulés par les jeunes du centre de formation qui ont fait leurs preuves: Grégory Leca, Grégory Proment, Sylvain Marchal, Eric Hassli et Stéphane Morisot hélas victime d'une rupture du ligament croisé antérieur en cours de saison. Du côté des transferts, Faryd Mondragon, l'impressionnant gardien international colombien réussi la lourde tâche de faire oublier Lionel Létizi parti relever un nouveau défi au PSG. Patricio d'Amico épaule quant à lui Gérald Baticle, arrivé à l'intersaison la saison précédente en provenance de l'AJ Auxerre , ainsi que Jonathan Jager, à la pointe de l'attaque.

Après un bon début de saison qui vit notamment Eric Hassli faire une entrée fracassante dans le monde professionnel, la formation lorraine s'enlise en queue de peloton. Manquant de panache offensif, les Messins comptent sur l'arrivée de l'espoir colombien Tressor Moreno pour retrouver des couleurs. Joël Muller n'aura que trop peu l'occasion de domestiquer le talent brut du Sud-Américain. Il est limogé à l'intersaison après de longues années au service du FC Metz. Albert Cartier, son adjoint, reprend les rennes de l'équipe. Grâce notamment aux prouesses exceptionnelles de Faryd Mondragon dans les buts, il parvient à maintenir le club parmi l'élite.

Pourtant, ce n'est que retarder l'échéance. L'année suivante, le club conserve sa confiance en l'équipe en place, cette dernière ayant réalisé une deuxième partie de saison plus que satisfaisante (4ème sur les matches retour). Malheureusement, la formation messine, l'effet de surprise et Faryd Mondragon en moins, ne parvient pas à confirmer les promesses entrevues quelques mois auparavant. Du coup, après une élimination catastrophique de la Coupe de France à Libourne (CFA2) au moins de janvier, Carlo Molinari actionne à nouveau le siège éjectable. Dirigée par Gilbert Gress, l'équipe retrouve un style de jeu pimpant et spectaculaire mais perd de sa solidité défensive. Metz ne tirera pas non plus profit de ses nombreux matches en retard (5) dus aux conditions climatiques difficiles en hiver. Le couperet tombe le soir de l'ultime journée de championnat. Metz concède le nul face à Lorient dans un stade Saint-Symphorien comble mais finalement médusé. Après trente-cinq saisons passées au plus haut niveau, Metz retrouve la seconde division. Sans l'assurance de pouvoir s'en relever...