Первый храм в честь святителя Николая Чудотворца был построен в селе Нижнекаменка в 1898 году. Это было деревянное здание с одним престолом, возведенное на средства прихожан. В состав прихода входили село Нижне-Каменское, деревни Ерестная и Усть-Хмелевская. С 1911 года при храме действовала церковно-приходская школа. В 1937 году, в период антирелигиозной политики советского государства, храм был закрыт по постановлению Облисполкома № 837 от 26 мая 1937 года. Здание храма было переоборудовано под клуб, что подтверждается «Списком церковных зданий недействующих православных церквей, находящихся в Новосибирской области и г. Новосибирске на 1 июня 1945 года», где указано: «с. Нижнекаменка. Клуб.»
В 1997 году, после распада Советского Союза и возрождения религиозной жизни в России, в селе Нижнекаменка была построена новая деревянная церковь во имя святителя Николая Чудотворца. Архитектурно здание представляет собой небольшую одноглавую церковь со звонницей, в объемных формах восходящую к зодчеству Русского Севера. Строительство храма было осуществлено на средства прихожан.