La Chiesa parrocchiale venne costruita dal 1516 al 1520, quando si determinò la necessità di provvedere ai bisogni spirituali della popolazione, in seguito all'espansione del territorio urbano del Comune. A questa nuova Chiesa vennero trasferiti tutti i diritti e le prerogative della prima Chiesa di Santa Maria di tutte le Grazie, ricostruita dagli albanesi alla loro venuta in Mezzojuso.
Per il permesso ottenuto il 26 marzo del 1537 dall'Arcidiocesi di Palermo, la chiesa, ormai piccola ed angusta, venne abbattuta e sullo stesso posto ne venne costruita una più grande, secondo le esigenze cultuali del rito greco; lo testimoniano, tra l'altro, le visite pastorali eseguite dagli arcivescovi di Palermo, sotto la cui giurisdizione cadeva la chiesa, per esempio la visita fatta dall'Arcivescovo Palafox e Cardona nel 1684.
Altra testimonianza ce la fornisce il papas Nicola Chetta di Contessa Entellina, il quale, nel 1740, scrive che la Chiesa di S. Nicolò e quella di Santa Maria di Mezzojuso sono le uniche due chiese in perfetto stile bizantino esistenti nelle colonie greco-albanesi di Sicilia.
La chiesa, nel 1732, sotto l'arciprete Figlia, fu sottoposta ad importanti opere di restauro; l'iconostasi rimase in piedi, venne smontata più tardi alla fine del secolo XVIII, quando si provvide ad adattare la Chiesa ai gusti del tempo.
Le icone vennero appese ai muri della Chiesa e vi rimasero fino al 1900, quando vennero quasi tutte trasferite nella Chiesa di Santa Maria di tutte le Grazie.
Rimangono in San Nicola quattro grandi icone del XVI secolo raffiguranti rispettivamente: San Nicola, San Giovanni Battista, San Basilio il Grande e San Giovanni Crisostomo. Ancora si conserva una icona di piccole dimensioni della madre di Dio; ed un'altra assai interessante ed unica nel suo genere per il suo contenuto teologico liturgico, sempre sulla Madre di Dio, che illustra l'inno dell'Epa si chèri (In tesi rallegra).
Nel 1850 venne restaurato il prospetto della Chiesa ed altri importanti lavori di restauro vennero eseguiti negli anni 1933-1934. L'altare interno, di tipo basilicale, venne fatto costruire nel 1938 con elementi marmorei del vecchio. Su di esso poggia un tabernacolo sormontato da un crocifisso d'avorio su croce di ebano del XVII secolo, dono del Principe Corvino, benefattore della Chiesa.
Negli anni 90 de secolo scorso, grazie alla volontà dell'Arciprete papas Francesco Masi ed al generoso contributo dei fedeli è stata ripristinata l'iconostasi con le icone provenienti dal studio iconografico di K. Zouvelos di Atene.
La Parrocchia dal 1937 appartiene alla giurisdizione ecclesiastica dell'Eparchia di Piana degli Albanesi.
Fonte:
Eparchia di Piana degli Albanesi,
Annuario Diocesano 1970, 111-112.
1599 Papas Andrea Lascari
1627 Papas Paolo Papadà
1641 Papas Giuseppe Reres
1642 Papas Ignazio Dimarco
1665 Papas Girolamo Cuccia
1681 Papas Silvestro Schirò
1697 Papas Anzelmo Schirò
1728 Papas Nicolò Figlia
1770 Papas Melchiorre Masi
1775 Papas Francesco Cuccia
1821 Papas Nicolò Dragotta
1839 Papas Lorenzo Cavadi
1886 Papas Antonio M. Figlia
1904 Papas Onofrio Buccola
1926 Papas Lorenzo Perniciaro
1975 Papas Francesco Masi
2008 Papas Marco V. Sirchia
2010 Papas Pietro Lascari
2016 Papas Giorgio R. Caruso