Archikatedra jest trzecim łacińskim kościołem biskupim w Przemyślu. Pierwszą katedrą (1375-1412) był drewniany kościółek pw. Świętych Piotra i Pawła. Drugą (1412-1460) kościół z kamienia na Zamku. Budowę obecnej katedry w stylu gotyckim rozpoczął bp Mikołaj Błażejowski w 1495 r. Ostały się tylko mury i filary. Odbudowę wraz z wyposażeniem wnętrza zakończono w pierwszych dziesiątkach XVI wieku. W 1578 r. 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. Przebudowana została w stylu barokowym przez bp. Aleksandra Fredrę. Roboty rozpoczęto w roku 1728. W prezbiterium umieszczono ołtarz barokowy i nowe stalle, pozostawiając jednak gotycką konstrukcję wnętrza z pilastrami i żebrowaniami sklepienia. W nawach wymieniono filary sklepienia, poszerzono okna, sprawiono barokowe ołtarze i konfesjonały, położono marmurową posadzkę, ściany i gzymsy pokryto 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. W 1733 r. runęło sklepienie nawy głównej i jeden filar. Odbudowę zakończono w 1744 r. za bp. Wacława Sierakowskiego, który też 15 sierpnia tego roku dokonał ponownej konsekracji katedry.

W roku 1883 bp Łukasz Solecki podjął dzieło gruntownej restauracji świątyni według projektu arch. Tomasza Prylińskiego. Prezbiterium przywrócono gotycki charakter przez odsłonięcie 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 bp. Józefa Sebastiana Pelczara.

W roku 1928 zakupiono wielki organ firmy Biernackich. W 1941 r. spłonął od niemieckich pocisków dach katedry z sygnaturką, 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 zbudowana została w latach 1759-1764. W roku 1907 podwyższono ją i nakryto barokowym hełmem. W roku 1960 z okazji 500-lecia rozpoczęcia budowy katedra otrzymała od Stolicy Apostolskiej tytuł bazyliki mniejszej. Przy okazji renowacji wnętrza bazyliki (1968-1972) odsłonięto na sklepieniu prezbiterium zabytkową polichromię renesansową z połowy XVI wieku.