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.