Obecna Bazylika jest trzecim łacińskim kościołem biskupim w Przemyślu. Pierwszą katedrą od formalnej erekcji diecezji w roku 1375 stanowił do 1412 roku drewniany kościółek pod wezwaniem świętych Piotra i Pawła, stojący na placu obok dzisiejszego kościoła Najświętszego Serca Pana Jezusa. Jako druga katedra służyła od 1412 – 1460 roku kościół z kamienia ciosowego na Zamku.
Budowę obecnej katedry w stylu gotyckim rozpoczął wraz z Kapitułą biskup Mikołaj Błażejowski w 1495 roku. Ostały się tylko mury i filary. Odbudowę wraz z wyposażeniem wnętrza zakończono w pierwszych dziesiątkach XVI wieku.
W 1578 roku starosta przemyski Jan Tomasz Drohojowski ufundował obecną kaplicę Najświętszego Sakramentu. Gotycka katedra służyła biskupom przemyskim do początku XVIII wieku. Nadwerężoną zębem czasu w konstrukcji i ozdobie wnętrza postanowił przebudować, zgodnie z upodobaniem swej epoki w nowym stylu barokowym, biskup Aleksander Fredro (+1734). Roboty rozpoczęto w roku 1728. w prezbiterium umieszczono potężny Wielki Ołtarz barokowy i nowe stalle, pozostawiając jednak gotycką konstrukcję wnętrza z pilastrami i żebrowaniami sklepienia. Natomiast w nawach wymieniono filary sklepienia, poszerzono okna, sprawiono barokowe ołtarze i konfesjonały, położono marmurową posadzkę, ściany i gzymsy pokryto jasną polichromią z bogatymi złoceniami. Z frontu dobudowano okazały portyk, z boku zaś od strony południowej kaplicę z kryptą grobową dla rodziny Fredrów. Kiedy przebudowa dobiegała końca, przyszła katastrofa. W Niedzielę Zapustną 1733 roku po nabożeństwie runęło sklepienie nawy głównej i jeden filar. Odbudowę zakończono w 1744 roku za biskupa Wacława Sierakowskiego, który też 15 sierpnia tegoż roku dokonał uroczyście ponownej konsekracji katedry.
W tej barokowej szacie służyła ona diecezji po koniec XIX wieku, kiedy to w roku 1883 biskup Łukasz Solecki podjął znów dzieło gruntownej restauracji swej świątyni według projektu architekta krakowskiego Tomasza Prylińskiego. Prezbiterium przywrócono pierwotny gotycki charakter przez odsłonięcie z zewnątrz spod tynku ciosowego muru i szkarp, wydłużenie okien i zaopatrzenie ich w kamienne maswerki oraz witraże projektu Jana Matejki. Sprawiono neogotycki Wielki Ołtarz i stalle. Nawy pozostawiono w baroku, ale wymieniono w nich ołtarze i ambonę, ściany naw i prezbiterium oraz filary otoczono dębową boazerią. Całe wyposażenie drzewne wnętrza wykonał Ferdynand Majorski z Przemyśla. Polichromią wnętrze katedry pokrył Tadeusz Popiel z Krakowa. Restaurację ukończono za biskupa Józefa Sebastiana Pelczara.
W roku 1928 na Powszechnej Wystawie Krajowej w Poznaniu zakupiono wielki organ firmy Biernackich. 25 czerwca 1941 roku spłonął od niemieckich pocisków artyleryjskich dach katedry z piękną sygnaturką i uległy zniszczeniu matejkowskie witraże. Dach (bez sygnaturki) odbudowano w ciągu paru miesięcy, nowe witraże sprawiono w ostatnich latach. Dwa z nich (św. Jan Chrzciciel w Wielkim Ołtarzu i św. Stanisław Biskup) projektował Mehoffer, trzy środkowe prof. Wojciechowski z Krakowa.
Wieża katedralna zbudowana została w latach 1759 – 1764. w roku 1907 staraniem biskupa Józefa Sebastiana Pelczara podwyższono ją i nakryto wspaniałym barokowym hełmem, tak że stanowi prawdziwą ozdobę miasta.
W roku 1960 z okazji 500-lecia rozpoczęcia budowy otrzymała katedra od Stolicy Apostolskiej tytuł Bazyliki Mniejszej.
Kartony według projektu J. Mehoffa wykonał Kasper Pochwalski.
Przy okazji renowacji wnętrza bazyliki (1968 – 1972) odsłonięto na sklepieniu prezbiterium zabytkową polichromię renesansową z połowy XVI wieku.