La structure originale était un édifice catholique romain connue sous le nom d’église Sainte Marie. La construction gothique commença à la fin XIV siècle en 1383. En 1421, elle fut quasiment détruite par les Turcs peu avant la fin de sa construction. Après diverses modifications et interruptions, le chantier prit fin au XV siècle en 1477. Le service catholique fut remplacé par le service luthérien durant la Réforme protestante. La structure fut partiellement détruite lors de l’incendie allumé par les forces Habsbourg, le 21 avril 1689 durant la guerre contre les ottomans. Suite a cet événement, La cathédrale devint l’Église Noire. Une grande partie de la structure interne fut modifiée au cours du XVIII siècle tranchant avec le style originel.