Die erste dem Apostel Petrus gewidmete Kirche an dieser Stelle wurde bereits um das Jahr 1180 von MarkgrafKonrad Otto im romanischen Stil errichtet. Von diesem Bau ist noch die Krypta erhalten. 1296 wurde St. Peter zum Sitz des Kollegiatstifts von Brünn.
Während des Dreißigjährigen Krieges wurde die Stadt Brünn 1643 und 1645 erfolglos von den Schweden belagert. Hierbei wurde die Kirche durch Kanonenfeuer stark beschädigt und brannte nieder. Die Türme stürzten ein. Zwischen 1651 und 1652 wurde die Kirche zunächst nur notdürftig hergestellt, 1743–1746 dann nach Plänen des Architekten Moritz Grimm umfangreich erneuert.
1777 wurde St. Peter und Paul zur Bischofskirche des durch PapstPius VI. neu gegründeten zweiten mährischen Bistums Brünn. Zu diesem Anlass wurde der Innenraum der Kirche im Barockstil neu gestaltet. Aus dieser Zeit stammt unter anderem die monumentale Kanzel.
Zwischen 1889 und 1891 wurde die Kirche um ein neogotischesPresbyterium erweitert und ein neuer elf Meter hoher Altar hinzugefügt. Auch die Glasfenster mit Szenen aus dem Leben der Kirchenpatrone Petrus und Paulus stammen aus dieser Zeit. Die heute charakteristischen Türme wurden erst 1901–1909 durch den Wiener Architekten August Kirstein erbaut. Kirstein hatte sich mit seinem Entwurf gegen 41 Mitbewerber durchgesetzt.
Das Mittagsläuten findet in der Kathedrale nicht um 12 Uhr, sondern bereits eine Stunde früher um 11 Uhr statt. Der Legende nach hatten die Schweden versprochen, die Belagerung der Stadt am 15. August zur Mittagszeit abzubrechen. Im Verlauf der Schlacht entschieden die gewitzten Brünner daher, bereits um 11 Uhr zu läuten, und so zogen die Schweden unverrichteter Dinge ab.
