Stavební historie brněnské katedrály sahá od 12. až do 20. století a každé z nich v ní zanechalo svou stopu. Středověká stavební fáze byla završena v prvním decenniu 16. století, kdy k východu orientovaný chrám na skalnatém návrší v centru Brna získal téměř už svůj nynější půdorysný rozsah. Původně byl zasvěcen pouze sv. Petrovi (také kopec, na němž stojí, se nazývá Petrov), rozšířené patrocinium sv. Petra a Pavla se poprvé uvádí v roce 1378. Důležitá barokní přestavba podle návrhu Mořice Grimma byla realizována v letech 1743–1746. Původně farní kostel, při němž v roce 1296 olomoucký biskup Dětřich založil kolegiátní kapitulu, se stal katedrálou po ustavení brněnského biskupství v roce 1777. Ke stému výročí této události založil biskup Karel Nöttig stavební fond na dostavbu věže katedrály. Neogotickou přestavbu chrámu zpočátku vedl dómský stavitel a diecézní stavební rada August Prokop, žák vídeňského profesora a propagátora neogotiky Friedricha von Schmidta. Podle Prokopova návrhu byl v letech 1889–1891 regotizován barokní presbytář, včetně vybavení, a celkově upraven exteriér, mimo jiné byly vsazeny neogotické okenní kružby. K další fázi úprav, jež měly zahrnovat Schmidtem doporučovanou výstavbu věže v západním průčelí, ovšem nedošlo, neboť ji odmítl biskup František Saleský Bauer – jak kvůli nedostatku místa, tak kvůli odlišnosti od převládající typologie katedrál.
Rozhodnutí o pokračování neogotické přestavby přinesla v roce 1901 architektonická soutěž, v níž bylo posuzováno 42 návrhů. Autorem vítězného projektu s heslem „Super hanc petram“ (Na této skále) se stal vídeňský architekt August Kirstein, rovněž Schmidtův žák. Podle zadání soutěže měla pokračovat úprava interiéru katedrály, zejména její lodi, a zároveň měl být proměněn exteriér – s důrazem na dominantní roli stavby v siluetě města. Zvýšení věže situované při severní straně lodi se připravovalo již od roku 1877, nakonec byla paradoxně snížena, aby nekonkurovala nově vztyčenému dvojvěží. V rámci soutěže byly ověřovány různé varianty přistavění věží, přičemž zvolené Kirsteinovo řešení, realizované v letech 1904–1905, tedy již za biskupa Pavla hraběte Huyna, bylo oceňováno zejména ze dvou důvodů: 1) bylo získáno pro katedrály typické dvojvěží, byť nikoli na obvyklém místě v západním průčelí, zde by pro ně bylo málo místa; 2) umístěním věží po stranách presbytáře došlo k žádoucímu optickému zkrácení jeho délky. Tradované tvrzení, že dvojvěží navázalo na základy románských věží, ovšem neodpovídá skutečnosti. Nová silueta presbytáře byla dotvořena sanktusníkem. Neogotická úprava exteriéru pokračovala v letech 1906–1908: tehdy byly fasády po osekání omítek obloženy pískovcem z Padochova u Oslavan a osazeny kamenicko-sochařskými prvky z jemnozrnného hořického pískovce, také byla postavena kanovnická sakristie. Navržená regotizace interiéru lodi nakonec kvůli nedostatku peněz nebyla uskutečněna, což s povděkem kvitovala památková péče. Největší proměnou tak prošlo hlavní průčelí – členěné trojdílným oknem a završené trojúhelným štítem –, před něž byl předsazen sloupový portikus. Významná role tu byla přisouzena sochařským dílům vytesaným podle sádrových modelů Jana Kastnera z Prahy.
V přestavbě katedrály August Kirstein vyšel z vrcholně gotických vzorů – s důrazem na konstrukční jasnost i vznosnost –, přičemž některými prvky směřoval k secesi, a svým řešením dvojvěží s úspěchem dotvořil typickou dominantu Petrova i celého města.
Aleš Filip