Dlouhá historie kostela sv. Petra a Pavla na Vyšehradě začíná po roce 1070, kdy zde Vratislav I. založil kapitulu. Tehdy se začalo s výstavbou kapitulního chrámu. Byla to trojlodní bazilika s arkádovým předdvořím a kryptou. Od svých počátků se stal pohřebním, neboť od konce 11. století tady byli pohřbíváni přemyslovští panovníci. V roce 1249 vyhořel a následně opraven.

Pravděpodobně v roce 1370 byl takřka celý zbořen a na jeho místě vystavěna trojlodní bazilika s řadou pravoúhlých kaplí po stranách bočních lodí. V roce 1495 došlo k opravě a v roce 1565, při další úpravě, byla bazilika nově zaklenuta. Kapitulní kostel se koncem 16. století dočkal přístavby nového presbyteria a počátkem 17. století nové sakristie. K velké barokní přestavbě došlo v letech 1723-1729 pravděpodobně s použitím plánů stavitele Františka Maxmiliána Kaňky. Kostel byl bez věží, pouze na střeše sanktusníková věžička se zvonem. Na hřbitově pak byla samostatná zvonice s cibulovitou střechou a lucernou ukončenou křížkem.

S blížícím se koncem 19. století bylo rozhodnuto o radikální přestavbě kostela sv. Petra a Pavla v novogotickém slohu. Proběhla v letech 1885-1887 podle projektu arch. Josefa Mockera a později v jejím rámci, již za vedení arch. Františka Mikše bylo vybudováno nové průčelí a vztyčeny obě 58 m vysoké věže. Ty jsou římsami členěny na pět podlaží. Spodní patra mají hrotitá okénka, v nejvyšších dvou poschodích jsou dvojice velkých hrotitých profilovaných oken. Dřevěné krovy nahrazují prolamované kamenné žebrové stany, jejichž základním tvarem je osmihran. Nároží doplňují pylony, na nejvyšším místě jsou kamenné růžice. Po severní a jižní straně věží jsou přístavky sahající do výše tří podlaží, v nichž jsou schodiště na kůr a do vlastních věží.