En début de saison, l'ASPTT Metz présente un visage très remanié : Zita Galic et Sophie Hugard ont quitté le club, tandis que Joël Monasso prend la succession d'Olivier Krumbholz sur le banc. Le recrutement voit l'arrivée de la gardienne tchèque Lenka Černá et de la jeune espoir Nodjalem Myaro, couplée au retour marquant de la mythique Corinne Krumbholz. Cet exercice 1995-1996 inaugure également une nouvelle rivalité au sommet du handball français, l'ES Besançon supplantant désormais l'ASM Gagny comme principal rival des Mosellanes. Le démarrage s'avère poussif, marqué par une élimination dès le deuxième tour de Coupe d'Europe face à Budapest et une défaite d'entrée en championnat contre Dijon. Les Messines montent néanmoins en puissance au fil des semaines, enchaînant les succès probants comme face à Béthune (34-19) ou lors d'une démonstration contre Gagny (33-11). En finale du championnat, Metz confirme sa montée en gamme en dominant Besançon au terme d'une série disputée au meilleur des cinq matchs, décrochant ainsi le 6e titre de champion de France de son histoire.