Желанието на хората от селото да имат свой църковен храм датира от много години преди изграждането му. През 2015 г. Кметският екип на инж. Живко Георгиев възложи изготвяне на технически проект за нова църква. През 2016 г. техническият проект е одобрен и получава разрешение за строеж. Архитектът е Сергей Михайлович Киорогло, а конструктор е инж. Младен Върбанов от Каварна.
Притворът е отворен, вграден в основната конструкция на сградата чрез арки .
Изпълнението стартира в началото на 2017 година, а изпълнител на строителните дейности е „Добруджа Билдинг“ ЕООД гр. Добрич. Строителството продължи три години.
За изграждането на храма Община Тервел задели 123 хиляди лв., а други 15 хиляди лв. бяха събрани от дарители, чийто имена са съхранени в паметната книга, поставена в залата. Иконостасът е от липова дървесина, с дълбока ажурна резба.Изработен е от майсторско ателие „Ваневи“ - Велико Търново. Същото ателие през 2010/2011 г. изработи иконостаса на храма в Тервел. Камбаната на новокаменската църква бе пренесена от малка църква в с. Орляк, в която е служил покойният отец Добри от с. Жегларци.
Денят ни напомня и за голямата дарителска кампания, която кмета на селото Маринела Димитрова организира. Благодарение на нея денят на освещаването на новия храм прераста в земляческа и родова среща на всички фамилии от Нова Камена. Тук инж. Симеон Симеонов връчи званието „Почетен гражданин на Тервел“ на подполк. Ради Радев – главен диригент на българската армия и на Представителния гвардейски духов оркестър. В празничния ден бе организирана богата програма с участието на местния фолклорен изпълнител Петър Петров, ДФТА „Калинка Вълчева“ и Хор „Св. Георги“.