En 1865 os veciños de Vilalba acordaron construír unha igrexa nova. A que había quedaba pequena e estaba deteriorada. Por noticias posteriores sabemos que tiña a fachada románica de finais do século XII rematada por unha espadana para dúas campás e que se construíra, abeirada a ela na parede sur, no século XVII, unha torre para emprazar o reloxo que sostiñan os veciños. A pouca fortuna ao erguer a torre provocou que aparecese unha fenda na parede da igrexa e que ameazase caer.
A dicir de crónicas posteriores a torre máis ben parecía un pombal, resultaba un arrimo antiestético e con suprimila tíñase solucionado o perigo. Tamén se afirmaba que para amañar a parede da igrexa abondarían 500 pesetas e que de conservarse e construírse a nova noutro lugar habería dúas. En todo caso o edificio non parecía moi sólido. En 1697 houbo que reconstruílo. En 1711 gastáronse 134 reais en dúas trabes coas súas tesoiras, dúas ducias de cangos, cravos e dous carros de lousa para reparala. A esta cantidade houbo que sumarlle 124 reais por xornais a razón de 4 reais por día e aínda outros 75 por alimentos para os transportistas da madeira. As reparacións, sobre todo no lousado, continuaron cos anos.
Chama a atención o gasto realizado en 1854 por un total de 11 reais, o mesmo que custaba daquela un ferrado de centeo, para pagar ao mamposteiro Manuel Lodeiro quen debeu pechar o burato que uns ladróns fixeran na parede. Aportemos máis datos. A parroquia de Vilalba comprendía un territorio moi limitado: desde Os Castros á porta de Cima; de alí á fonte das Donas; de alí, seguindo o rego, ata a ponte da Magdalena; de alí ata Portonovo; de alí a Augada; de alí á fonte das Fontiñas; e de alí aos Castros. Como parroquia estaba asimilada á de Sancovade compartindo párroco.
No censo de 1762 só contaba cunhas 375 almas, igual que en 1809, pero en 1842 xa eran 800 e chegaron a 2.700 en 1910. É dicir, a pequena vila de Vilalba coas casas rodeando o castelo non medrará ata a segunda metade do século XIX, cando se estableza máis xente aproveitando o despegue económico das feiras e das transaccións comerciais que chegaron da man da construción de estradas e pontes.
A vella igrexa resultaba pequena. Comparándoa con outras románicas do rural, sabendo que se emprazaba no mesmo lugar ca actual, que se podía andar todo ao redor e que non chegaba á muralla da vila, podemos deducir que tería unha capacidade duns 70 metros cadrados, semellante á capela de san Roque de hoxe. E se lle restamos os 15 ou 20 metros cadrados do presbiterio e sabendo que tiña altares laterais e a presenza de reclinatorios ou bancos, deducimos que só caberían uns setenta ou oitenta fregueses. E iso para os máis de 1000 habitantes de 1865 non parece abondo.
Coa decisión de construír a nova igrexa veu a de derrubar a antiga e edificala no mesmo solar e coa mesma orientación leste-oeste. E apareceron problemas loxísticos. O espazo estaba limitado pola propia praza Maior á que daría a fachada e pola muralla e desnivel que ocuparía a cabeceira. Para facer sitio derrubouse a muralla, ocupouse o seu espazo e houbo que salvar un desnivel de cinco metros e medio.
Ter que construír unha enorme cimentación para salvar o desnivel e asentar o edificio ocasionou que só nesa obra se gastasen os cartos dispoñibles e que fose necesario reformular a intención de construír unha igrexa parecida á dos Remedios de Mondoñedo. Dunha fachada barroca labrada en pedra con semicolumnas e volutas debeuse pasar a un austero deseño neoclásico de custes máis axustados.
As obras avanzaron lentas. A capela de san Roque, co cemiterio no adro ata 1878, facía as funcións de parroquial. Os domingos de feira a misa oficiábase desde o balcón do antigo hospital de santa Catarina, e cando as condicións atmosféricas o permitían, as celebracións eran ao aire libre nunha ara instalada na propia praza Maior.
Hoxe, 125 anos despois da súa inauguración, descoñécense libros ou rexistros dos gastos realizados que ofrezan datos da edificación da actual igrexa de Santa María. Unha placa recorda que foi acabada en 1893 sendo senador o conde Pallares e deputados por esta circunscrición Fernando Cos-Gayón e Germán Vázquez de Parga, sendo Cos-Gayón quen, como ministro de Graza e Xustiza, concedeu os recursos necesarios.
O día de san Ramón dese ano consagrouna o bispo mindoniense, Manuel Fernández de Castro. Foron obras que duraron 28 anos, case tanto coma as dalgunhas catedrais.