Bazilika svatých Petra a Pavla stojí na Vyšehradě, jednom z nejstarších a nejdůležitějších míst českých dějin. Kostel byl založen českým králem Vratislavem II. v roce 1070 současně se založením vyšehradské kolegiátní kapituly, která zde existuje dodnes. O dvanáct let později, v roce 1088, byl chrám zasvěcen svatému Petrovi a později také svatému Pavlovi. Od počátku se jednalo o stavbu v románském architektonickém slohu.

Stavba prošla dlouhou řadou proměn. V roce 1129 byla za vlády knížete Soběslava I. rozšířena a zpevněna. O sto dvacet let později, v roce 1249, ji těžce poškodil požár. Kolem roku 1330 započala zásadní gotická přestavba, při níž kostel vyrůstal do délky 110 metrů a stal se největší sakrální stavbou tehdejší Prahy. Za panování císaře Karla IV., v roce 1369, následovala další přestavba, která utvářela chrám do podoby trojlodí s presbytářem, bočními kaplami a předsíní, která jej charakterizuje. Ve druhé polovině šestnáctého století byla zaklenuta hlavní loď.

Barokní změny přinesly léta 1707 až 1729, kdy dostalo chrám nové průčelí a presbytář novou klenbu. Kolem roku 1740 byla vybudována takzvaná Šancovská kaple. Nejviditelnější podobu však získal chrám na konci devatenáctého a počátku dvacátého století, kdy jej mezi lety 1885 a 1887 přestavěl Jozef Mocker v novogotickém stylu s neobvyklou vnitřní secesní výzdobou. Průčelí pak v letech 1902 až 1903 realizoval František Mikš. Právě v té době vznikly charakteristické dvě věže vysoké 58 metrů, které se staly ikonickou dominantou Prahy a vytváří jednu z jejích nejrozpoznávanějších siluet. Tehdy byla odstraněna barokní zvonice z roku 1678.

Chrám je dnes novogotickou trojlodní pseudobazilikou s monumentálním západním dvojvěžím. Průčelí se třemi katedrálními portály je zdobeno zemskými a kapitulními znaky. Ve středu je reliéf, po stranách se nacházejí moderní mozaiky s motivem prvního a posledního písmene řecké abecedy od Lumíra Šindeláře. Na severním portálu připomíná pamětní deska českého sochaře Josefa Kadlčíka z roku 1941 historickou událost pokřtění čtrnácti českých knížat v Řezně roku 845. Vnitřek tvoří křížově klenuté trojlodí se secesními malbami svatých. Kaple jsou vybaveny mariánskými a ostatkovými oltáři. V Šancovské kapli se čtenář setkává s barokní dřevěnou sochrou Panny Marie s Ježíškem, která je považována za uzdravující. Schránka ve východní stěně kaple obsahuje údajné pozůstatky Přemyslovců.

Nejznámějším uměleckým pokladem baziliky je kopie gotického deskového obrazu Panny Marie Vyšehradské z poloviny čtrnáctého století, jeden z nejstarších českých dochovaných středověkých obrazů. Od roku 1638 je madona nazývána dešťovou a měl by být přímluvkyní za déšť. Originál obrazu je zapůjčen Národní galerii.

V druhé polovině dvacátého století, v letech 1981 až 1994, prošel chrám generální rekonstrukcí a opravou doprovázené archeologickým průzkumem. V roce 2001 byly na věže instalovány osmnáct nových zvonů, které doplnily dva původní zvony z baroka, a vznikla zvonkohra hrající různé melodie přizpůsobené charakteru Vyšehradu a církevnímu roku. O dva roky později, v roce 2003, povýšil papež Jan Pavel II. chrám na baziliku minor. Kostel je součástí areálu Vyšehradu, který je od roku 1962 chráněn jako národní kulturní památka. Hřbitov u kostela byl v devatenáctém století přeměněn na národní pohřebiště.