Według kanonika i zarazem sławnego kronikarza średniowiecznego, Jana Długosza, kielecki kościół ufundował w roku 1171 biskup krakowski Gedko (ok. 1130-1185), poświęcił może kolejny z biskupów, bł. Wincenty Kadłubek prawdopodobnie w 1213 roku - wtedy też przeniesiono do niej parafię z najstarszego kieleckiego kościoła p.w. św. Wojciecha. W połowie XIII wieku farę odnowiono po pożarze, który strawił ją być może w czasie najazdu Konrada Mazowieckiego (1244). Zapewne od początku istniała przy tym kościele kapituła czyli zgromadzenie księży sprawujących Służbę Bożą oraz tworzących rodzaj rady, pomagającej biskupowi w zarządzaniu diecezją i jej majątkiem; ta kielecka składała się początkowo z siedmiu, później zaś z dziesięciu członków (czterech prałatów: prepozyt, czyli proboszcz, dziekan, scholastyk i kustosz oraz sześciu kanoników), którym pomagali wikariusze, tworzący tzw. kapitułę mniejszą.
Jak można przypuszczać w oparciu o wykopaliska i wzmianki zawarte w źródłach archiwalnych, kościół kielecki był początkowo skromną, kamienną, dwuwieżową budowlą przykrytą sklepieniem tylko nad głównym ołtarzem, w nawie zaś stropem; ze świątyni tej zachowały się niektóre kamienne ciosy, wykorzystane przy budowie nowego prezbiterium w XVIII stuleciu, a także resztki ceramicznych płytek posadzkowych o roślinnej i geometrycznej dekoracji. W 1514 roku biskup krakowski Jan Konarski (1447-1525) dobudował do prezbiterium piętrową, murowaną zakrystię, służącą też jako kapitularz, czyli miejsce zebrań kapituły kolegiackiej. Inny biskup krakowski, Piotr Myszkowski (ok. 1510-1591), w roku 1583 wydłużył świątynię ku zachodowi - zapewne wybudował obecną nawę główną (informuje o tym tablica wmurowana dziś pod chórem muzycznym).
W 1 połowie XVII wieku, a ściśle w latach 1629 -1634 - dzięki funduszom kapituły oraz datkom pochodzącym od wiernych - przystąpiono pod nadzorem wikarego, a później kanonika kieleckiego Macieja Obłomkowicza (1580-1654) do wnoszenia obecnego korpusu nawowego. W roku 1632 umieszczono nowy portal w narożniku północno-zachodnim, dwa lata później (25 listopada 1634) gotowy już kościół poświęcił biskup sufragan krakowski Tomasz Oborski (ok. 1570 - 1645); przy czym w roku 1635 zamontowano jeszcze w fasadzie zachodniej marmurowy portal ufundowany przez biskupa krakowskiego kardynała Jana Alberta Wazę (1612-1634), syna króla Zygmunta III. Z inicjatywy biskupa krakowskiego Kazimierza Łubieńskiego (1652-1719) wiosną 1719 roku rozpoczęto budowę nowego prezbiterium; prace kontynuowane po śmierci biskupa pod nadzorem kanonika kieleckiego Kazimierza Weissa i brata biskupa, podstolego koronnego Bogusława Łubieńskiego, zakończono ponownym poświęceniem kościoła, dokonanym 18 kwietnia 1728 roku przez biskupa Konstantego Felicjana Szaniawskiego (1668-1732).
Z jego inicjatywy otoczono też cmentarz nowym ogrodzeniem z dwoma bramami, podwyższono dzwonnicę, wreszcie wystawiono ganki - system komunikacyjny łączący północne skrzydło pałacu z kolegiatą, szkołą i seminarium. Począwszy od ok. 1726 roku stopniowo wymieniono wszystkie ołtarze; niewykluczone, iż przy projektowaniu kilku z nich zatrudniony był znany architekt Kacper Bażanka (zm. 1726), przy realizacji zaś krakowski snycerz Antoni Frąckiewicz (zm. 1741), uczeń Baltazara Fontany (zm. 1733) znakomitego włoskiego artysty czynnego m.in. przy dekoracji kościoła Św. Anny w Krakowie.
Istotne zmiany zarówno wewnątrz, jak i na zewnątrz świątyni nastąpiły już w XIX i XX stuleciu - w latach 1869-1872 pod nadzorem proboszcza Józefa Ćwiklińskiego i według projektu architekta Franciszka Ksawerego Kowalskiego (1827-1903) zmieniono wschodnią i zachodnią elewację kościoła, przebudowując je w stylu neobarokowym, urządzono kruchtę północną w miejscu dawnej kaplicy z chrzcielnicą, położono nową posadzkę oraz wystawiono wysoką sygnaturkę - także dzieło F. K. Kowalskiego, który zaprojektował również obecną kaplicę Najświętszego Sakramentu (1894-1895) w nawie północnej. Wnętrze pokryła polichromia - w 1827 roku Karol Boehm po raz pierwszy pomalował prezbiterium, po raz drugi dokonał tego Antoni Strzałecki z Warszawy (1892); w latach 1898-1899 grupa malarzy krakowskich - Piotr Niżyński, Kasper Żelechowski, Franciszek Bruzdowicz, Leonard Strojnowski i Stefan Matejko - wykonała zaś polichromię korpusu nawowego, a pomiędzy 1912 a 1914 rokiem pomalowano kaplicę Pana Jezusa oraz uzupełniono dekorację prezbiterium (Piotr Niżyński, bracia Cholewińscy).
W 1805 roku kościół po raz pierwszy podniesiono do godności katedry, kiedy to ustanowiono diecezję kielecką, która przetrwała do roku 1818, biskupem kieleckim był wówczas Wojciech de Boża Wola Górski (1739-1818); ponownie - i ostatecznie ustanowiono biskupstwo kieleckie w roku 1882; pierwszym biskupem został wówczas Tomasz Teofil Kuliński (1823-1907).
W 1971 roku podniesiono katedrę kielecką do godności bazyliki mniejszej, a w 1982 uznano ją za ogólnodziecezjalne Sanktuarium Maryjne. Począwszy od 1997 roku dzięki staraniom proboszcza, ks. prałata Stanisława Kowalskiego trwały w kościele zakrojone na szeroką skalę prace konserwatorskie, w wyniku których m.in. odnowiono elewacje zewnętrze wraz z kamieniarką, dzwonnicę i kaplicę Ogrójcową, we wnętrzu zaś restaurowano wszystkie ołtarze, stalle, lożę biskupią, ambonę, ławki (z dodaniem nowych, wykonanych na wzór XVIII-wiecznych), ważniejsze epitafia i starsze obrazy, częściowo wymieniono posadzkę w prezbiterium wraz z obniżeniem poziomu podestu pod ołtarzem, w oknach naw bocznych zamontowano witraże ufundowane przez prywatnych ofiarodawców; w trakcie prowadzonych w kościele prac, odkryto dawną polichromię w kruchcie północno-zachodniej, przedstawiająca Apostołów.
Katedra kielecka nawiązuje stylem do innych, wcześniejszych budowli głównie z terenu Małopolski - monumentalne filary dostawione do ścian nawy i prezbiterium, wspierające sklepienne arkady (tzw. system ściennofilarowy) wzorowały się i na XVI wiecznej architekturze włoskiej, i na budowlach małopolskich z początków XVII stulecia (m.in. kościół Dominikanów w Klimontowie, 1617-1620), za przykładem klasztoru w Klimontowie (może i kościołów sandomierskich), wprowadzono też charakterystyczny typ sklepiennej dekoracji naw bocznych, łączący wzory lubelskie i krakowskie; do budownictwa krakowskiego odwoływały się też formy elewacji, a przede wszystkim architektonicznego detalu (m.in. portali), wprowadzone do sztuki polskiej przez włoskiego architekta Jana Trevano (zm. 1642) i kontynuowane w warsztatach kamieniarskich Chęcim Pińczowa czy Wąchocka. W przypadku dobudowanej po 1719 roku części wschodniej powtórzono w zasadzie formy korpusu, dodając jednak we wnętrzu pełne przęsła, na elewacjach zaś pilastry.
Katedra kielecka pozostaje dziełem anonimowym - nie znane są nazwiska projektanta ani XVII- ani XVIII-wiecznej części; być może przy budowie nowego prezbiterium (1719) zatrudniony był Kacper Bażanka, architekt pracujący dla biskupa Konstantego Felicjana Szaniawskiego, któremu niektórzy badacze przypisują również projekty seminarium duchownego, południowego skrzydła pałacu i niektórych ołtarzy katedralnych.
