На месте нынешней церкви Рождества Пресвятой Богородицы в селе Вийтовка в 1745–1774 гг. стоял деревянный храм Святого Иоанна Златоуста, но он сгорел при пожаре. В 1873 году на его месте поставили новую кирпичную церковь с такой же колокольней. В 1892 году начала работу церковно-приходская школа, организованная священником Никитой Громачевским. Она действовала до 1964 года.
В храме сохранились иконы XIX столетия, написанные уроженцем села Гнатом Петришиным, который учился живописи в монастыре на горе Афон. Возле церкви похоронен упокоившийся в 1804 году известный борец за утверждение православия на Подолье отец Василий Мокрицкий – первый православный священник Вийтовки.
В 1935 году церковь лишили колоколов, правда, часть из них удалось спрятать. Богослужение продолжалось до праздника Пасхи 1938 года и возобновилось только с 1976 года. В церкви прекрасный двухъярусный иконостас – главное украшение храма. В 1980-х гг. были заново расписаны стены.
В середине 1990-х гг. сгорела колокольня. Ее отстроили в течение года, но при пожаре погиб весь церковный архив, а с ним и летописи, которые велись священниками. В восстановлении и реставрации церкви постоянную помощь оказывают прихожане, местное руководство, предприниматели.