Достовірно невідомо час закладення православної парафії на Белзькому передмісті Кам'янки-Бузької, що звалась Кам'янкою-Струмиловою від імені фундатора міста Юрія Струмила. Вперше 1451 року в гродських актах було згадано дяка неназваної церкви Сенька. 1564 року згадані церкви Св. Миколая і П'ятницька, яка до XVIII ст. зникла з сторінок документів. У XVII ст. у Кам'янці-Струмиловій був закладений монастир з церквою Благовіщення. До наших днів дійшла церква Св. Миколи і мурована Різдва Пресвятої Богородиці з 1870-х років. 1789-го парафію церкви св. Миколи приєднали до парафії церкви Різдва Пресвятої Богородиці.

Сьогоднішня будівля церкви походить з 1667, що засвідчує напис від 21 вересня 1667 на порталі південних дверей . На той час власником міста був Ієроним Радзейовський. Тоді церкву з соснового дерева з дубовими підвалинами збудували чи ґрунтовно перебудували. Церковне братство затвердив 27 квітня 1689 єпископ Йосиф Шумлянський і підтвердив у липні 1738 митрополит Атанасій Шептицький. Церкву відновили 1759 року, 1867-го під неї підвели фундамент з каміння, посилили стіни. У церкві зберігся п'ятиярусний іконостас XVII ст. Намісні ікони несли датування 1618, апостольський ряд з 1660-х років, частина з межі ХІХ-ХХ ст. Церква була пошкоджена в час боїв Першої світової війни і відновлена.

Церкву реставрували 1962 року за проектом Ігоря Старосольського, 1971 — за проектом Л. Дмитрович. На час першого обстеження церкви фахівцями 1971 у церкві бракувало 5 ікон. Незабаром було викрадено решту ікон. У бабинці перебувало два невеликі вівтарі XVIII ст. з багатим різним декором. 1898 розписали інтер'єр церкви, поновили ікони, іконостас, для якого виготовили двоє дияконських дверей. 1905 маляр Йосиф Сидорович з Монастириська розписав всю церкву, відновив іконостас, виконавши до нього 5 ікон, зокрема намісну ікону Св. Миколи.

Дерев'яна тризрубна триверха церква має високу квадратну наву, більш низькі п'ятистінний бабинець і вівтарну частину з бічними невеликими криласами. Церква має опасання, три високі верхи на восьмериках. Дахи покриті ґонтом, який перекрили листами бляхи.

Біля церкви розміщена дерев'яна дзвіниця каркасної конструкції. Напис на порталі дверей засвідчує 1762 за рік будівництва. Вірогідно, того року лише відновили дзвіницю, збудовану одночасно з церквою. Відомо, що 1880 її ремонтував майстер Андрій Ґоронцій, добудувавши захристя.

За «совітів» у ній діяв музей атеїзму.