Na wzgórzu, w miejscu, gdzie dzis stoi katedra, w X i XI w. znajdował sie drewniany kościół pw. św. Mikołaja, rozebrany pod koniec XI w. W drugiej połowie XII w. staraniem Kazimierza Sprawiedliwego wzniesiono kolegiatę romańską pw. Narodzenia Najświętszej Maryi Panny, poświęconą w 1191 r. Kościół ten został zniszczony w czasie najazdu tatarskiego w 1259 r.

Obecna świątynia pochodzi z XIV w. z fundacji Kazimierza Wielkiego, wybudowana ok. 1360 r., została uroczyście poświęcona w 1382 r.

W poł. XV w. kolegiata została powiększona o kaplicę Mansjonarską (obecnie kaplica Najświętszego Sakramentu) ufundowaną przez biskupa Zbigniewa Oleśnickiego.

W 1717 r. przeniesiono parafię z kościoła św. Piotra do kolegiaty.

W 1818 r. utworzono w Sandomierzu stolicę biskupią i dotychczasowa kolegiata otrzymała tytuł katedry. W 1960 r. Ojciec Święty Jan XXIII nadał katedrze tytuł bazyliki mniejszej.

W 1934 r. biskup Włodzimierz Jasiński przeniósł parafię z katedry do kościoła pw. św. Józefa w Sandomierzu.

W 1982 r. biskup Edward Materski wydzielił część miasta z parafii pw. św. Józefa oraz część z parafii pw. Nawrócenia św. Pawła i utworzył parafię katedralną.

Parafia posiada księgi parafialne (ochrzczonych, zaślubionych i zmarłych) od 1982 r.

Wcześniejsze księgi parafialne od 1720 r. do 1941 r. znajdują się w Archiwum Diecezjalnym, ul. Katedralna 1, 27-600 Sandomierz, tel.:  15/ 644 53 53.