Arkikatedra pastatyta parapinės bažnyčios (minima 1413 m.) vietoje. Ji XV ir XVI a. buvo kelissyk remontuojama, plečiama ir rekonstruojama. XV a. bažnyčiai priklausė šv. Mikalojaus, šv. Gertrūdos koplyčios, šv. Kotrynos altarija, žemės sklypai Kleboniškyje, Eiguliuose, Žemaitkiemyje, Rumšiškėse. Barbora Juškienė 1525 m. altarijai dovanojo Šėtijų palivarką, 2 mūrinius namus. Margarita Ačėnaitė 1531 m. dovanojo mūrinį namą.
1579 m. bažnyčiai skyrė turto Steponas Batoras, 1680 m. – Jonas Sobieskis. 1602 m. Kražių komendorius kunigas Petras Burniška bažnyčiai dovanojo 2 namus. Bažnyčia buvo statoma miestiečių lėšomis bei didikų fundacijomis, todėl statybos raidoje atsispindėjo miesto ekonominio klestėjimo ir nuopolio metai.
XVI a. išmūryta zakristija su krištoliniais skliautais. 120 metų parapinė bažnyčia stovėjo neužbaigta. Tik 1624 m. karališkasis sekretorius ir Pajūrio tijūnas Jeronimas Krišpinas-Kiršenšteinas paskyrė statybai 10 000 auksinų. Iki 1650 m. pagrindiniai darbai baigti, pastatytas masyvus bokštas. Paaukštinus vidurinę navą, bažnyčia įgavo bazilikinę erdvę. Ji tapo didžiausiu Lietuvos gotikiniu pastatu.
1655 m. sudegė medinės konstrukcijos ir interjero puošyba. Vėliau atstatyta ir 1671 m. konsekruota. 1682 m. sumūryta šventoriaus tvora su dviem vartais. Per 1732 m. miesto gaisrą sudegė bažnyčios stogas, sugriuvo presbiterijos skliautai. Iki 1775 m. atstatyti skliautai, išdažytas vidus, įrengti altoriai, interjeras įgavo baroko bruožų.
1800 m. gaisras vėl apnaikino pastatą. Po gaisro restauruota šventovė iki šių laikų beveik nebepakito. 1808–1864 m. bažnyčia priklausė vienuoliams augustinams. Bažnyčia ir vienuolynas 1812 m. apiplėšti, jų vidus nuniokotas. 1820–1835 m. veikė parapinė mokykla. Valdžia, nesuderinusi su Vatikanu, 1864 m. bažnyčioje įkurdino Telšių (Žemaičių) vyskupijos katedrą. Popiežius 1884 m. sutiko perkelti ją.
1895 m., vyskupo Motiejaus Valančiaus rūpesčiu, popiežius Leonas XIII buvusiai parapinei bažnyčiai suteikė katedros – svarbiausios vyskupijos bažnyčios titulą. 1895 m. įvyko katedros perkėlimo iškilmės. Į jas vyskupui Aleksandrui Beresnevičiui valdžia atvykti neleido.
1887 m. architektas Florianas Vyganovskis parengė katedros rekonstrukcijos projektą. Pagal jį numatyta pastatyti du 113 m aukščio pagrindinio fasado bokštus. Projektas tik iš dalies įgyvendintas. Rekonstrukcijai vadovavo architektas Georgas Verneris. Pagal Ustino Golinevičiaus projektą 1879–1884 m. padidintas vargonų choras, pastatyti meistro J. Radavičiaus vargonai.
1893–1897 m. katedros pietryčių kampe pristatyta koplyčia, padidinta ir trisienė apsidė, užbaigta zakristija, perkeltos durys. Koplyčios statybą fundavo grafai Pšezdeckiai. Dailininkai Jonas Moniuška ir J.Čajevičius su pagalbininkais išdažė sienas ir lubas, nutapė paveikslų.
1921 m. Žemaičių vyskupijos įkūrimo 500 metų jubiliejaus proga popiežius Pijus XI katedrai suteikė bazilikos titulą. 1926 m. įsteigus Lietuvos bažnytinę provinciją, bazilika tapo arkikatedra su arkivyskupo metropolito sostu. 1937–1939 m. ir 1970–1976 m. pastatas atnaujintas. Dailininkai Bronius Uogintas ir Juozas Algirdas Pilipavičius 1976–1977 m. restauravo XVIII a. freskas. Jos XIX a. pabaigoje buvo uždažytos.