Le premier lieu de culte dédié à saint Etienne est un oratoire du Ve siècle. Il s'agrandit lorsque Metz devient capitale de l'Austrasie. La première cathédrale date du VIIIe siècle.
Une seconde cathédrale, de style ottonien, est consacrée en 1040. Pour des raisons liées au relief, elle a été construite perpendiculairement à l'édifice précédent, c'est à dire avec une orientation vers le nord-est, que conserve la cathédrale actuelle.
Le choeur ottonien a été conservé jusqu'au XVe siècle.

En 1186, une collégiale est construite contre l'extrêmité ouest de la cathédrale ottonienne : c'est l'église Notre-Dame-la-Ronde.

La nouvelle cathédrale est construite au début du XIIIe. Elle reprend le plan de l'édifice précédent. Peu après, l'église Notre-Dame-la-Ronde est reconstruite. Ses piliers sont dans l'alignement de la nef de la cathédrale. Au XIVe siècle, la cloison séparant les deux églises est abbattue, ce qui allonge la nef de trois travées et fait du choeur de Notre-Dame-la-Ronde une chapelle latérale.

C'est à cette époque qu'est aménagé le fenestrage de la façade occidentale. Les voûtes sont édifiées entre 1360 et 1380. On ne décide de reconstruire le choeur et le transept qu'en 1487. L'entreprise est terminée en 1522 et les vitraux sont posés en 1539.
Au XVIIIe siècle, un portail monumental est ajouté à l'ouest ainsi qu'un portique classique au sud. Ce dernier est supprimé au XIXe siècle. Quant au portail, il est remplacé en 1903 par un portail néogothique.