Узнікненне храма ў Вышаградзе шмат у чым звязана з барацьбой за ўладу ў другой палове XI стагоддзя паміж князем Ураціславам II і яго братам Ярамірам, біскупам Пражскім. Ураціслаў, жадаючы стварыць новы цэнтр улады, абраў сваёй рэзідэнцыяй Вышаград, дзе вырашыў заснаваць і царкоўную арганізацыю, незалежную ад Пражскай дыяцэзіі. У выніку ў 1070 годзе быў заснаваны незалежны ад пражскага біскупа Вышаградскі капітул, які падпарадкоўваўся непасрэдна Папе Рымскаму (капітул заставаўся незалежным да 1763 года), і закладзены касцёл Святых Пятра і Паўла, будаўніцтва якога, мабыць, працягвалася да 1080 года. Калі верыць хронікам, князь Ураціслаў асабіста ўдзельнічаў у будаўніцтве храма, даставіўшы 12 кошыкаў камянёў для падмурка.
Касцёл быў збудаваны ў выглядзе базілікі ў раманскім стылі і прызначаўся ў тым ліку для пахавання ў ім караля Ураціслава II і членаў каралеўскай сям'і. Лічыцца, што ў 1092 годзе кароль Ураціслаў быў пахаваны ў гэтым храме, аднак археалагічныя даследаванні не прывялі да выяўлення тут яго рэштак.
Напачатку 1129 годзе храм быў істотна пашыраны. У 1249 годзе ў храме здарыўся пажар, пасля якога касцёл быў адноўлены ў раннегатычным відзе.
Пры імператары Карле IV у 1369 годзе ў выніку маштабнай рэканструкцыі касцёл атрымаў выгляд гатычнагатрохнефнага храма з бакавымі капліцамі.
Падчас гусіцкіх войнаў у 1420 годзе Вышаград быў захоплены гусітамі і касцёл Святых Пятра і Паўла пры гэтым быў значна пашкоджаны. У 1495 годзе пасля канчатковага аднаўлення храм быў нанова асвячоны.
Апошняй перабудовай храма стала распачатая ў 1885 годзе рэканструкцыя ў неагатычным стылі. Яе аўтарам стаў вядомы архітэктар Ёзеф Моцкер. На тымпане над галоўным уваходам у храм Штэпанам Залешакам у 1901 годзе быў выразаны рэльеф на тэму «Страшнага суда». Будаўніцтва скончылася ў 1902—1903 гадах, калі былі пабудаваны дзве неагатычныя пярэднія вежы, названыя «Адам» і «Ева», праект якіх быў выкананы архітэктарам Францішкам Мікшам. Пасля завяршэння рэканструкцыі храм атрымаў яго сучасны выгляд.
Інтэр'ер храма
Інтэр'ер базілікі мае шмат упрыгажэннямі ў форме сцянных арнаментаў і фігурных роспісаў у стылі мадэрн, выкананых Францішкам Урбанам і яго жонкай Марыяй у 1902—1903 гадах. Прэзбітэрый распісаны фрэскамі венскага мастака Карла Ёбста, якія адлюстроўваюць сцэны з жыцця Святых апосталаў Пятра і Паўла.
У першай капліцы знаходзіцца каменны саркафаг у раманскім стыліXII стагоддзя. Паводле легенды ў ім знаходзяцца рэшткі Святога Лонгіна, але насамрэч у ім быў пахаваны адзін з прадстаўнікоў дынастыі Пржэмысловічаў.
У другой капліцы храма знаходзіцца алтар чэшскіх заступнікаў. У трэцяй капліцы на алтары знаходзіцца знакамітае пано Дажджавой Дзевы Марыі, помнік гатычнага жывапісу сярэдзіны XIV стагоддзя. Пано захоўвалася ў калекцыях Карла IV і Рудольфа II, а ў 1606 годзе было падорана храму Святых Пятра і Паўла. Паводле падання, абраз Дажджавой Дзевы Марыі быў намаляваны самім евангелістам Лукой. У часы засухі да абраза Дзевы Марыі прыходзілі працэсіі з маленнямі аб дажджы. На сцяне левага бакавога нефа можна бачыць барочную фрэску з краявідам Вышаграда, напісаную каля 1420 года.
У 1988—1994 гадах інтэр'ер храма быў істотна перароблены, што запатрабавала немалых выдаткаў.