Tout est à reconstruire, François Remetter est transféré au FC Sochaux, mais le club a la chance de pouvoir compter sur de nombreux jeunes joueurs formés en son sein, tels " Dédé " Hess et sa crinière légendaire, Jean-Claude Kuhnapfel, Roland Steibel, l'inamovible René Fuchs, Serge Zénier (père de Bernard Zénier). Les cadres de l'équipe sont Alberto Corazza, l'élégant gardien, Antonio Acosta, l'avant-centre paraguayen à l'abondante moustache noire, Wladyslaw Grabkowiak, sans oublier, bien sûr, les Claude Dosdat et Henri Burda Le club à la Croix de Lorraine reste trois saisons durant au " purgatoire " de la Deuxième division avant de retrouver l'élite, (après deux saisons moyennes achevées à la 6ème place) grâce à une excellente 2ème place obtenue à l'issue de la saison 1960-1961, derrière la SO Montpellier qui ne l'emporte qu'au goal-average (un but d'écart seulement). L'équipe messine qui remonte cette année là en Première Division est entraînée par un personnage truculent, haut en couleurs : le hongrois Jules Nagy, dit " La Jules ". Un autre personnage, capable du meilleur comme du pire, marque les supporters de cette époque : Santiago, dit " Diego " Bessonnart. Doté d'une classe exceptionnelle, d'une virtuosité fabuleuse, cet international uruguayen sait absolument tout faire : jongler, distribuer et marquer. Parmi les joueurs on retiendra Marcel Husson, Roland Ehrhardt, les frères Jules et Georges Zvunka, Michel et Jean-Louis Heinrich, l'international France-Espoirs Jean-Paul Scheid et Jean Vagneur...

Malheureusement Diego Bessonnart ne reste pas au F.C. METZ - il y reviendra en 1963-1964 et la saison de retour en première division est immédiatement suivie d'une nouvelle descente aux " abîmes ". Comme un malheur n'arrive jamais seul, au cours de cette saison 1961-1962, le FC Metz inscrit sur ses tablettes la plus cuisante défaite des grenats en championnat : 11 - 2 face au Racing Club de Paris et perd un de ses plus fidèles serviteurs, Claude Dosdat (12 ans d'ancienneté), capitaine courageux du " onze " messin, contraint d'abandonner la pratique du football à cause d'une hernie discale. Seule note brillante de la saison 1961-1962 : un comportement satisfaisant en Coupe de France : une victoire en ¼ de finale remportée sur l'AS Monaco à la 91e minute, alors que l'on joue les arrêts de jeu. La rencontre se déroule à Bordeaux et le but est marqué par un autre " Grand Monsieur " du football : l'élégant international danois Jorn Soerensen qui évolue alors aux côtés des Pierre Tillon (un ancien du RC Paris), Ernst Stojaspal (international autrichien) et Stéphane Walczak. Les messins terminent la saison 62-63 9èmes de Division 2, puis 3èmes la saison suivante derrière Lille et Sochaux (Diego Bessonnart revenu au FC Metz après un séjour à Nîmes n'y est pas étranger) ; malheureusement c'est insuffisant pour retrouver l'élite car le FC Metz se classe 4ème et dernier en matchs de " barrage ". Le F.C. METZ piétine toujours et le fidèle public de Saint-Symphorien commence à désespérer.

C'est dans ce contexte de morosité qu'intervient un événement de grande importance : le 15 juillet 1965, Raymond Herlory, après 33 années consacrées au club à la Croix de Lorraine, fatigué et quelque peu amer décide de passer le relais à Paul Mayer, en se contentant de la présidence d'honneur. Il conserve, bien sûr, ses fonctions au sein des instances nationales, mais le destin ne lui laisse guère de répit puisqu'en ce jour fatal de mars 1966, Raymond Herlory succombe à une crise cardiaque. Quelques heures auparavant, il s'est entretenu au téléphone de son cher vieux FC Metz avec Paul Mayer...

Tout un symbole... Un an plus tard, à l'issue de la saison 1966-1967, le FC Metz, se classe bon deuxième derrière Ajaccio et obtient ainsi son " ticket " pour ce que l'on appelle encore la " Division nationale ". L'entraîneur d'alors Max Schirschin et les joueurs : Jean-Marie Lawniczak, Jean Molla, Roger Helf, Georges Zvunka, Michel Heinrich, Auguste Kouadjo, Roger Niesser, Roland Massucci, Marcel Husson, Claude Hausknecht et Anton (Antoine) Rudinski, ont donné le meilleur d'eux-mêmes, mais cette accession le club la doit en grande partie au fidèle René Thil, compagnon de route de feu Raymond Herlory.

Depuis le début de la saison la lutte est chaude en tête entre Ajaccio, Bastia et Metz, mais à trois journées de la fin, les messins perdent à domicile un match décisif contre Chaumont, hypothéquant toute chance d'accession parmi l'élite. Les efforts de toute une saison allaient s'envoler, mais grâce à une parfaite connaissance des textes du règlement, René Thil offre à son club une victoire sur " tapis vert ". Il l'obtient en déposant, avant le match, des réserves quant à la qualification du gardien de but chaumontois, Christian Laudu dont la licence " amateur " a été enregistrée hors délai. Les efforts de toute une saison allaient s'envoler, mais grâce à une parfaite connaissance des textes du règlement, René Thil offre à son club une victoire sur " tapis vert ".D'abord débouté en première instance, le club messin, sur de son bon droit, tient jusqu'au bout et, en appel, devant les plus hautes instances du Groupement, fait triompher ses arguments.

Le président Paul Mayer, considérant avoir atteint ses objectifs - ramener les " Grenat et Blanc " parmi l'élite, sortir le club de l'indifférence populaire, revaloriser l'équipe - et en raison d'obligations familiales et professionnelles, remet, le 21 juin 1967, les destinées du club à la Croix de Lorraine entre les mains d'un industriel, jeune et dynamique, un passionné de sport en général et du football en particulier : Charles Molinari, originaire de Villerupt, ancien champion de France civil et militaire de moto-cross, un fonceur lucide et raisonné, un impulsif sachant se tempérer ; bref, un homme de parole, fidèle, attachant, trapu, solide et franc.