TürmeDie Heidentürme sind an der westlichen Seite im romanischen Teil. Ihr Name kommt von dem minarettartigen Aussehen. Sie sind mit dem Riesentor der älteste Teil des Domes.
Der Südturm ist der ausgebaute, hohe Turm, an der Basis ein viereckiger Bau, der sich immer mehr verjüngt und allmählich in ein Achteck übergeht. Auf dem Absatz, aus dem schließlich die Spitze nach oben strebt, stellen 12 Fialentürmchen die 12 Apostel dar. In den unteren Geschoßen befanden sich früher Glocken. Auch die Pummerin hing einst in ihm. An der Spitze steht ein zweiarmiges Kreuz. Bei starkem Wind kann der Turm bis zu 10 cm schwanken, bei starkem Sturm sogar bis zu 30 cm!
Auf etwa halber Höhe auf dem Weg in die Türmerstube befindet sich im Stiegenhaus das „Starhembergbankerl“, von dem aus während der zweiten Türkenbelagerung die Bewegungen des Feindes beobachtet wurden. An der Fassade des Turmes findet man einen Türkenkopf und eine türkische Kanonenkugel.
Der Nordturm wurde erst nach Fertigstellung des Südturmes begonnen. Bei den Fundamenten verwendete man zum Löschen des Kalkes Wein statt Wasser. Es ist Tatsache, dass dadurch die Stabilität des Kalkes höher wird. Nach dem Bau des Fundamentes ließ man es 17 Jahre lang ruhen. 1511 erreichte man die gegenwärtige Höhe. Nach der Sage ist der Teufel Schuld, dass der Turm nicht höher wurde. 1578 bekam der Nordturm die Renaissancehaube, die heute die Pummerin beherbergt.
