L'église Saint-Martin est mentionnée pour la première fois vers 850. Ce premier édifice a été érigé en remployant partiellement le rempart romain du IIIe siècle, dont on peut encore apercevoir les assises.

L'église est reconstruite dans les premières décennies du XIIIe siècle. Le narthex est érigé vers 1210-1220 dans le style roman. Le reste de l'église est de style gothique. La nef, réalisée vers 1220-1230, est l'un des rares témoignages en Lorraine du gothique primitif. En raison des caractéristiques de ce style, qui tend à élever les bâtiments vers le ciel, la nef est plus haute que l'avant-nef. Le chœur et le transept ont été construits au début du XVIe siècle, dans le style du gothique flamboyant.

L'église Saint-Martin subit d'autres transformations au cours de son histoire, notamment au XIXe siècle. Le bas-côté droit et le bras sud du transept sont amputés en 1817 pour percer la rue Lasalle. Une partie du transept et du chœur sont repris en 1878. Enfin, en 1887, l'architecte allemand Conrad Wahn réalise un nouveau clocher, de style néogothique en remplacement du précédent avait été démoli en 1565, lors de la construction de la citadelle. Ce nouveau clocher comporte notamment quatre statues d'angles représentant les Évangélistes.

L'édifice renferme une sculpture gothique du XIVe siècle, située dans une niche du bras nord du transept. Elle représente la Nativité, lorsque la Vierge allaite l'Enfant Jésus.

Les vitraux témoignent des différentes périodes d'aménagement de l'édifice. Les baies du transept datent pour la plupart des XIVe, XVe et XVIe siècles. On peut notamment y observer, dans le bras nord, une Passion du Christ du milieu du XVe siècle. Dans le chœur, des verrières de Laurent Charles Maréchal et de Charles François Champigneulles, réalisés entre 1878 et 1881, sont consacrés à la vie de saint Martin.