История Новохарьковки начинается с 1750-1760 годов, с момента прихода на эту землю крестьянина из посёлка Ольховатка — Самотоевского. Именно по этой причине сегодня местные жители называют её Самотоевкой. Прежними названиями Новохарьковки были хутор Самотоев и слобода Харьковская. На сегодняшний день Новохарьковка — слобода Ольховатского муниципального района Воронежской области.
В 1855 году в Новохарьковке была построена каменная Спасская церковь, а уже к 1900 году в слободе имелись 2 общественных здания, церковно-приходская школа, 21 ветряная мельница, маслобойный завод, 5 мелочных лавок и винная лавка.
Сведений о храме мало. Учителем церковно-приходской школы был Михаил Григорьевич Смыкалов. Церковь разрушили в 1964 году. Оставшиеся после разрушения церкви каменные глыбы пошли на строительство сельского Дома культуры, здания сельской администрации и почты.