Diecezja przemyska została utworzona przez Grzegorza IX w roku 1375. Jej pierwszym pasterzem był biskup Iwan. Jego siedzibą mógł być Przemyśl, Krosno lub Rzeszów. Początkowo diecezja podlegała bezpośrednio Stolicy Apostolskiej. Następcą biskupa Iwana w Przemyślu został dominikanin Mikołaj, zwany Rusinem (Nicolaus Rutenus), przeor dominikańskiego klasztoru w Sandomierzu, pochodzący zapewne z diecezji przemyskiej. Jego nominacja na biskupa przemyskiego nastąpiła za życia papieża Klemensa VI (14 maja 1352).

25 marca 1992 r. Jan Paweł II dokonał reorganizacji administracji kościelnej na ziemiach polskich. Bullą Totus Tuus Poloniae Populus ustanowił między innymi nową metropolię przemyską. W jej skład weszły: archidiecezja przemyska oraz nowo utworzone diecezje: rzeszowska i zamojsko-lubaczowska. Pierwszym metropolitą przemyskim został mianowany ksiądz arcybiskup Ignacy Tokarczuk, który przez 27 lat kierował diecezją. Po jego przejściu na emeryturę, Ojciec Święty powołał na stolicę przemyską księdza arcybiskupa Józefa Michalika, dotychczasowego biskupa zielonogórsko-gorzowskiego, który jest w kolejności 68. biskupem ordynariuszem przemyskim. W pasterzowaniu w archidiecezji wspomagają go biskupi pomocniczy: Marian Rojek i Adam Szal. Na terenie archidiecezji pracuje także arcybiskup senior Ignacy Tokarczuk.
Jan Paweł II, podczas swojej pierwszej w dziejach archidiecezji przemyskiej wizyty w Rzeszowie i Przemyślu (2 czerwca 1991 r.) wyniósł do chwały ołtarzy jednego z ordynariuszy tej diecezji - biskupa Józefa Sebastiana Pelczara (1900-1924). 10 czerwca 1997 roku, Ojciec Święty Jan Paweł II kanonizował w Krośnie patrona diecezji, św. Jana z Dukli, a podczas pielgrzymki do Ojczyzny w roku 2002 w dniu 18 sierpnia na krakowskich Błoniach beatyfikował ks. Jana Balickiego.

Obecna bazylika archikatedralna obrządku łacińskiego jest budowlą trzynawową o wystroju barokowym zespolonym z gotyckim prezbiterium. Rozpoczęcie budowy pierwszej katedry przypadło na lata zarządu diecezją przemyską przez biskupa Mikołaja Błażejowskiego (1452-1474). Na skutek kłopotów finansowych udało mu się ukończyć jedynie prezbiterium, po czym na wiele lat budowa została wstrzymana. Prace wznowiono pod koniec XV wieku - w ich wyniku wymurowano nawę główną, a całość budowli pokryto dachem. W czasie jednego z licznych w owym czasie napadów Tatarów na miasto w 1495 roku wybuchł wielki pożar, który zniszczył dopiero co ukończoną świątynię. Na początku XVI w. podjęto prace remontowe. Wobec powtarzających się na początku XVI wieku zbrojnych napadów na miasto, katedrze nadano charakter obronny. Ostatecznie wykończono kościół w roku 1549. XVII wiek, ze względu na liczne wojny, nie sprzyjał pracom przy rozbudowie miasta i jego kościołów. Dopiero przemyski ordynariusz Aleksander Antoni Fredro (1724-1734) rozpoczął wielki remont świątyni katedralnej. Po zawaleniu się jej sklepienia w 1732 r. ostateczną odbudowę ukończono w 1744 r. Kościołowi przywrócono poprzednie wezwanie Najświętszej Maryi Panny, Wszystkich Świętych i św. Jana Chrzciciela. Czas zaborów przyniósł kilkakrotne rekwizycje majątku katedry. Kolejne przebudowy i remonty miały miejsce na przełomie XIX i XX w.