Že leta 1970 je arhitekt Janez Valentinčič naredil načrte za novo cerkev, a je tedanja krajevna oblast temu nasprotovala.
Šele ob nastopu demokracije v Sloveniji so bile razmere zrele tudi za novo grahovsko cerkev. Leta 1992 so se začela pripravljalna dela. Pod taktirko župnika Metod Lampeta, arhitekta Franceta Kvaternika in izvajalca gradbeno podjetje SCT so dolgoletne sanje postale resničnost. Še istega leta 11. oktobra je škof Jožef Kvas blagoslovil temeljni kamen za novo Marijino cerkev na mestu prejšnje in le dobra dva meseca kasneje so tudi prvič po pol stoletja praznovali v njej tudi Božič. Na tiho nedeljo leta 1993 so zapeli tudi novi štirje bronasti zvonovi. Blagoslovil pa jih je tedanji ljubljanski nadškof Alojzij Šuštar.
Zgodovinski dan pa je nastopil 27. aprila leta 2000, ko je cerkev Marijinega Brezmadežnega spočetja dobila dokončni izgled in bila po rokah nadškofa Franca Rodeta tudi posvečena.
Jeseni 2009 pa je po daljšem času prišlo do zamenjave in nov župnik je postal Sandi Osojnik. Pred sto in več leti je bilo okrog župnijske cerkve tudi pokopališče, ki pa je danes zunaj naselja ob glavni cesti v smeri proti Novi vasi.