Bien avant que la construction de la cathédrale ait commencé, le site avait été le carrefour entre l'ancien centre de la ville, un marché et probablement aussi une chapelle. Toutefois, les cultes ont eu lieu au château de Bratislava, où le chapitre et le prévôt avaient leur siège.
Comme la sécurité du château était menacée, le roi Imre de Hongrie a demandé au pape Innocent II l'autorisation de déménager le bureau du prévôt ce qui fut fait en 1204. L'église a été déplacée en 1221, et a été construite dans le style Roman et sanctifié au Saint-Sauveur. Comme la ville se développait de plus en plus, surtout après qu'elle a reçu des privilèges en 1291, elle est devenue insuffisante pour les célébrations de la ville, et sur sa place (avec un vieux cimetière), la construction d'une nouvelle cathédrale gothique a commencé en 1311. La construction ne s'est terminée qu'en 1452 pour des raisons financières, et la construction a même été arrêtée en raison des guerres hussites. En 1452, l'église a été recouverte d'un toit et consacrée, toutefois, les travaux de construction ont continué tout au long de XVe et XVIe siècles:
- Un nouveau presbytère a été construit entre 1461 et 1497.
- Les chapelles gothiques de la Reine tchèque Sophie de Bavière et de Sainte-Anne ont été ajoutées au XV siècle.
- La chapelle baroque de Saint-Jean le Miséricordieux a été achevée dans la première moitié du XVIII siècle par Georg Rafael Donner.
- La célèbre sculpture équestre baroque de Saint-Martin par Georg Rafael Donner a été ajoutée en 1744.
- En 1760, le sommet de la tour gothique a été frappé par la foudre et, plus tard remplacé par un Baroque, qui a ensuite été détruit par un incendie en 1835 puis reconstruit en 1847 (avec quelques modifications), et surmonté de la couronne de saint-Étienne.
- L'église a pris son aspect actuel au cours de la période de 1869 à 1877, après avoir subi des dommages par le feu, la guerre, les tremblements de terre et autres catastrophes.
