La data della sua costruzione è incerta, ma si vuole eretta nel XII secolo, in seguito alla scissione tra i due gruppi etnici, Mariani e Nicoleti, avvenuta dopo la conquista normanna della Sicilia.
In una lapide posta sul portale principale si legge:
D.O.M.
Hoc opus fuit factum post partum Virginis actum
Dum numero decies demptis octuaginta centis
Est die nona Maij dicata aedes Nicolai.
Ossia: Quest'opera è stata eseguita dopo il parto della Vergine (cioè dopo la nascita di Cristo ) tolti 180 (anni) da 10 volte 100…e segnerebbe quindi la data dell'820; ma tale lapide proviene dall'antichissima chiesa di S. Nicolò le Petit,ergentesi vicino all'alto castello, e nel XII secolo, con le reliquie ed il culto del Santo fu trasferita nella chiesa più grande di nuova costruzione. Nel 1305 essa era ancora una <cappella sancti Nicolai de plano>.
L'edificio fu costruito dai cittadini nicosiani per l'aumento della popolazione del quartiere e forse lo spirito di emulazione rese necessaria una chiesa più grande.Ai tempi normanni essi dai piedi del castello scesero al piano. La costruzione, dunque risale ai secoli XIV e XV, come provano le date incise nella fabbrica.
La pace che seguì al trattato di Caltabellotta (1032), favorì l'inizio dei lavori. È di quell'anno la fusione della campana, che, rifusa <gravius mole> nel 1720, è la campana grande capitolare. La chiesa divenne funzionale, anche se non ancora ultimata, nel 1340, come si desume dalla iscrizione che sta sull'architrave della porta, chiamata del Monte , oggi in gran parte erosa:

+ANNO MILLENO TRECENTUM CUM [quadarageno::qui] MENTIS GRATIS DEDIT ERGOS
+VIRGINIS [intactae post partum: quam satis aptel:: INDE BEATI TENDUNT AD RE
+HOS NIXINUS [thomas lapides nicoxinus] : GNUM PARADISI JURE SUPERNORUM
+CONSTRUXIT VERE TU NOBIS REX MISERERE ::CONSERVET GENTEM NICOSIE FIRMIT EGE.

Nell' <area divi Nicolai>, stando almeno al Farzello, il re Pietro D'Aragona tenne il parlamento generale del Regno il 1O gennaio 1337, nel quale condannò a morte Francesco Ventimiglia, conte di Geraci.
La porta, ritenuta di stile lombardo, è chiusa da una cornice semicircolare a punte di diamante, cui sovrasta una finestra, la quale, rotonda in origine, deve la sua forma ellittica al rifacimento del 1600. La sua semplicità e l'arco ad unico raggio contrastano con la straordinaria ricchezza del portale maggiore a sesto acuto, segno apparente che le due porte appartengono a programmi architettonici diversi.
Inoltre la chiesa doveva essere distanziata dalla torre, di cui esisteva solo il primo piano (alcuni pensano che fosse un avamposto dei Saraceni). Sul fianco unito alla chiesa è ancora ben visibile, dalla scala di accesso, l'arco originale, e appare evidentemente posticcia anche all'esterno della la struttura che lega la torre alla chiesa. Quando, poi, la chiesa venne prolungata, la nave sinistra e parte della centrale vennero trovarsi a ridosso della torre, e fu quindi necessario spostare il portale, il quale è in posizione asimmetrica al centro della chiesa, e resta in parte nascosto dalla torre. Questa asimmetria è posta in risalto dal rosone in alto, che è assiale al centro della navata centrale.
Con la Bolla del 15/06/1521 la chiesa fu eretta da Papa Leone X in collegiata; e il 17/03/1817 con bolla di Pio VII venne eretta in Cattedrale; fu consacrata il 15/06/1856 da Mons. Milana (e di tale avvenimento fa fede una lapide posta di fronte all'ingresso della sacrestia); venne insignita del titolo e della dignità di Basilica Minore il 19/06/1967.
Il Governo italiano l'ha dichiarata Monumento Nazionale con R.D. del 21 novembre 1940.