В 1068 году князь Вратислав перенес княжескую резиденцию на Вышеград и сразу начал строить большой храм. По преданию, он своими руками принес 12 корзин с камнями для строительства. Князь покинул Пражский град и переехал в явышеград, сделав его центром государства, из-за крупных разногласий со своим братом, епископом Яромиром Гебхартом. Вратислав превратил деревянное городище, укрепленное земляными валами, в романскую крепость, построил княжеский дворец и костел Святых Петра и Павла. При костеле появился и капитул – коллегия каноников, то есть священников, совершавших в храме торжественные богослужения. Во главе капитула встал пробст – так на латыни именовали настоятеля храма или монастыря. Вышеградский капитул, в отличие от капитулов других церквей, подчинялся не пражскому епископу, а непосредственно Папе Римскому.
Сын Вратислава Собеслав I перестроил капитульный костел и богато его украсил – внутри появились росписи, новый пол из плитки, большая люстра из золота, серебра и бронзы.
В этом соборе после кончины Карла IV было выставлено его забальзамированное тело. Правда, сначала мертвый император одиннадцать дней находился в королевском дворце на Пражском граде, а уже потом его тело в сопровождении великолепной процессии стали перевозить в разные части Праги, чтобы проститься с правителем смогло как можно больше людей.
В 1420 году, во время гуситского мятежа, пражане разнесли почти всё в покинутом королевским гарнизоном Вышеграде. Костел сильно пострадал, крипта - подземная усыпальница - Пршемысловичей оказалась засыпана, и археологи впоследствии не смогли ее найти. Десятилетия храм оставался в плачевном состоянии. Проповеди гуситов-протестантов нашли отклик в душах жителей вышеградского подградья. Хотя храм юридически принадлежал католического капитулу, во второй половине XV века с ведения короля Владислава бургомистр городов пражских назначил на Вышеград протестантского проповедника, который причащал хлебом и вином, как полагалось по протестантскому обряду. У католиков же миряне причащались только Хлебом и лишь духовенство допускалось к Чаше с Вином. Потому гуситов-протестантов и стали называть "чашники". Собор Святых Петра и Павла некоторое время служил чашникам и только в конце XV века был заново освящен.
С западной стороны в храм ведут три входа, украшенных чешскими львами и моравскими орлицами, а средний вход – знаком Вышеградского капитула и львами. Стену над главным порталом украшает рельеф с изображением Страшного суда. Выше, по краям главного окна - мозаичные изображения Петра и Павла. Еще выше, в нишах фронтона - статуи Христа и апостолов. Деревянные изображения Петра и Павла, а также Кирилла и Мефодия, украшают главный алтарь.
Во время Первой мировой войны 8 колоколов вышеградской базилики были конфискованы для военных нужд. В апреле 1942 года власти протектората конфисковали оставшиеся колокола для снабжения немецкой военной промышленности цветными металлами. С башни костела были сняты небольшие колокола весом 59 и 38 килограммов. Два больших колокола, весившие две и три тонны, пришлось разбить прямо в колокольне, потому что они не проходили в окна. В результате конфискаций северная башня осталась вообще без колоколов, а в южной сохранились два исторических колокола. Один из них, названный "святые Петр и Павел", отлит известным мастером Брикци из Цимперка. Он не страдал от излишней скромности и оставил подпись: "Именитый Брикци, мастер колокольных дел из Цимперка, изготовил этот колокол в 1584 году". Надпись на втором колоколе сообщает, что его сделал Балтазар Гоффманн в 1621 году.
В конце XX века был разработан проект возвращения недостающих колоколов на башни базилики, а в 2001 году в соборе установили карильон - колокольный музыкальный инструмент.