Date precise de când datează o parohie în sat încă nu se cunosc, însă pe la mijlocul veacului al XVIII-lea, ca multe alte parohii unite vecine, comunitatea greco-catolică din Prilog apare ca activă. Mai înainte poate să fi fost filie la o altă parohie mai mare, cum a aparţinut administrativ în vremurile mai vechi de localitatea Vama. La început a aparţinut episcopiei unite rutene a Muncaciului, după care din 1853, anul înfiinţării Episcopiei greco-catolice a Gherlei – episcopie românească – a trecut sub jurisdicţia acesteia, având ca prim episcop pe Ioan Alexi. Cu data de 15 august 1932 înfiinţându-se Episcopia greco – catolică a Maramureşului cu sediul la Baia-Mare, având ca prim episcop pe Dr. Alexandru Rusu (episcop-martir mort pentru credinţă în 1963 la închisoarea din Gherla, beatificat în 2019 de către Papa Francisc la Blaj), parohia Prilog a fost trecută aici, făcând parte organică din aceasta până în anul 1948, anul interzicerii Bisericii greco-catolice de către regimul comunist.
Conform Şematismului Episcopiei greco-catolice a Maramureşului din 1936, Prilogul apare ca parohie veche, cu biserică din piatră cu hramul Naşterii Preacuratei Fecioare, a cărei zidire începe în 1850, şi cu o casă parohială făcută din văioage, ridicată în 1853. Matricolele parohiale sunt evidenţiate consecvent din 1832, iar în 1907 este construită din lemn şi şcoala confesională.
Biserica și casa parohială au fost din cele mai vechi timpuri aşezate aici, înconjurate de cimitirul vechi al satului. Se spune că au fost găsite mai multe oseminte umane cu ocazia zidirii pivniţei la casa veche parohială, sub pastorația preotului greco-catolic Ioan Pop Lemeny. Precum şi mai aproape de zilele noastre, au fost descoperite oseminte şi sicrie ale înaintaşilor cu ocazia zidirii noii case parohiale ortodoxe, în 1956, sub preotul Constantin Ioniţă. În vremurile vechi casa parohială a fost mai spre apus, la ceva distanţă, mai mică, faţă de poziţia actuală a casei parohiale ortodoxe. Noua casă parohială a fost făcută în 1956, fiind zidită, aproximativ, în acelaşi loc, unde a fost cea dinaintea ei, greco-catolică. În anii 1983-1984 sub preotul Ioan Pop s-a reconstruit noua casă parohială, din cărămidă. Biserica veche de dinainte de 1850, făcută din lemn, a fost după casa parohială, pe dâmbuşorul ce apare astăzi sădit cu pomi. Biserica actuală e zidită din piatră, în formă de navă, și a fost ridicată între anii 1850-1864.
Condeiul preotului Titu Borca dă mărturie despre activitatea lui și despre lucrările executate la biserică. Pentru strângerea fondului necesar lucrărilor ce urmau să se execute la biserică, menţionează în cronica citată sus-numitul preot, s-au vândut 900 bucăţi lemne din pădurea bisericii un preţ de 90.000 lei, precum și pădurea de la jugăre primită prin reforma agrară cu alte 90.000 lei, în total ajungându-se la suma de 180.000 lei. Planul de zidire a turnului și de transformare a bisericii l-a făcut arhitectul Iuliu Bredei din Satu Mare. Lucrările s-au început în 15 august 1934, lucrând la zidărie George Oşanu în calitate de antreprenor, Ludovic Lazim tinichigiu și Alexandru Senti lemnar, toţi din Seini. Cu suma de 180.000 lei s-a ridicat turnul în roşu, s-au pus burlanele la biserică, s-a făcut corul și baza de beton la începutul pârtilor de la turn în sumă de circa 60.000 lei. Crucea în vârful turnului s-a ridicat în ziua de 14 octombrie 1934. Lucrările s-au terminat în 20 octombrie 1935 și s-a făcut binecuvântarea bisericii, fiind delegat al episcopiei din Baia Mare preotul Ludovic Vida canonic la Baia Mare, asistat fiind de preoţii: Gheorghe Anderco, protopop al Țării Oaşului și Parohia Bixad, preot Augustin Pop ieromonah Mănăstirea Bixad, preot Ioan Androd paroh Racşa, preot Vasile Erdos paroh Lechinţa, preot Gheorghe Coman, paroh în Vama și parohul locului. Renovări mai mici la biserică s-au făcut în timpul pastoraţiei preotului Gheorghe Pop. Tot în timpul lui s-a ridicat la 10 iunie 1948 un monument din piatră neagră (aşezat cu faţa spre uşa bisericii) în cinstea eroilor căzuţi pe câmpul de luptă în timpul celor două războaie mondiale.
Biserica are patru clopote: unul din 1882 şi trei din 1929, toate aşezate în turnul bisericii.
Nicolae Ghișan
