По словам старожилов, в Новосёловке был большой храм с колокольней, освящённый приблизительно в 1865 году. Храм был построен богачём Худяковым. При храме была сторожка и колодец, который есть и по сей день. В 1938 году храм советские власти закрыли. Священников было 7 человек. Запомнили нынешние прихожане о. Михаила Грушу.

С 1941 года храм стали разбирать на разные хозяйственные потребности. Когда разбирали колокольню, то дети и присутствующие люди видели на воздухе свт. Николая, который махал рукой. Во время войны храм стоял разобранный до половины. После войны остатки храма были разобраны окончательно. Осталась одна сторожка, в которой долгое время была амбулатория.

По ул. Октябрьская службы шли в одном маленьком, стареньком домике. Батюшку, что там служил, звали о.Палладий, который похоронен на  местном кладбище.

В настоящее время под церковь отдали помещение бывшего сельского клуба, где служит новый батюшка о. Василий. До него служил о. Евгений, который начал строить новый небольшой храм. С большими усилиями, с Божьей помощью строительство храма продолжается. В 2010 году  установлен центральный купол. Освящён и установлен крест.

Источник: https://www.eparchia.kharkov.ua/churchinfo/105