Первую однопрестольную деревянную церковь во имя Николая Чудотворца построили в 1712 г., через 38 лет после основания поселения выходцами из Нижегородского уезда. В 1750 и 1890 гг. храм перестраивали и ремонтировали. В 1842 г. в его клир входили священник Александр Дмитриев Предтеченский и дьячок Павел Стефанов Лентовский, а в 1858 г. – священник Василий Яковлев Смелов и дьячок Иван Голосницкий.
В Национальном архиве Республики Татарстан хранится уникальный документ по истории Николаевской церкви – её главная опись, сделанная в 1899 году. Она интересна не только описанием существовавшей на этот момент деревянной церкви, покрытой железом и обшитой тёсом, длиной 19,2 м и шириной 6,4 м (с восемью окнами, двумя дверями, одной печью, без стенной живописи и т.д.), но и упоминанием строящейся новой каменной с железной крышей, длиной 32 м и шириной 21,4 м (по длине в 1,7 раза больше прежней, а по ширине – в 3,3 раза), с двадцатью окнами, четырьмя дверями, трехъярусной колокольней и двумя железными вызолоченными крестами. Деревянный храм был обнесён деревянной оградой на каменном фундаменте, а также имел 5 колоколов. Только на самом большом из них указывался вес (32 пуда 20 фунтов, или 533,2 кг) и содержались надписи следующего содержания: «завода Саратовских купцов, в городе Саратове братьев Гудковых, мастер Василий Кеменев, 1881 года» и «Благовествую земле радость велию, хвалите небеса Божию славу; благовестите день ото дня спасение Бога нашего; возлюбих благолепие дому твоего и место селения славы Твоея». Кроме того, на колоколе сверху были изображены херувимы, в середине – Божья Матерь, святитель Архангел Михаил и святители бессребреники Косьма и Дамиан.
При описании алтаря храма отмечалось, что он покосился от давности, а шёлковый жёлтый антиминс на престоле был освящён в 1885 г. Высокопреосвященнейшим Палладием, архиепископом Казанским. Там же находилась икона Тихвинской Божией Матери, а на горнем месте – икона нерукотворного образа Спасителя и другие предметы культа. Всего в алтаре насчитывалось 17 икон. В предалтарном трёярусном икононостасе, украшенном вызолоченными карнизами и резьбой, имелось 15 икон, в том числе весьма древняя икона Пророков с 4 ликами и стёршимися надписями. В других местах висели 27 икон, причём некоторые отличались древностью и богатым оформлением. Также в описи упоминаются 9 лампад, 12 подсвечников, 1 паникадило, 2 аналогия, 9 напрестольных крестов, 17 различных богослужебных сосудов, 32 наименования дарохранительниц и сопутствующих предметов, 4 кадила и другая обрядовая утварь. В ризнице хранились 6 Евангелий, самое старое из которых отпечатали в 1694 году в Москве, а остальные – в период с 1875 по 1896 годы.
Особый интерес вызывает опись книгохранилища, в которую входили: 1) одна Библия; 2) богослужебные книги: Праздничная минея 1767 г. и 3 писания святых отцов; 3) 14 книг духовного содержания; 4) периодические издания: журнал «Православный собеседник» за 12 лет (1863 – 1899 гг.), Церковные ведомости за 1889 – 1899 гг., Известия Казанской епархии за 1868 – 1899 гг. и т.д. Кроме того, в церкви находились метрические книги за 1782 – 1899 гг., духовные росписи за 1828 – 1899 гг., клировые ведомости за 1829 – 1899 гг. и другие документы. Жаль, что из всех перечисленных культурных ценностей до нас дошли лишь крохи…
Через 194 года после сооружения первого храма, в 1906 г. на средства прихожан построили новую однопрестольную каменную церковь, что говорит о неплохом благосостоянии сельчан в начале XX века. Должность священника исполнял Гаврила Александрович Троицкий.
Следующие документы по церковной истории Старой Грязнухи относятся к 1930 году. В апреле властями было решено снять с Николаевского храма 5 колоколов общим весом 1710,5 кг. В это время в нём числилось два служителя. Вскоре по постановлению Старомайнского райисполкома от 15 мая, по причине неуплаты страхового сбора в размере 544 рублей 82 копеек его закрыли. Однако верующие жители села активно боролись с произволом властей. 22 июня 1931 г. члены президиума районного исполкома слушали ходатайство Старогрязнухинского церковного совета о разрешении открыть церковь. В итоге они постановили возвратить её сельскому обществу верующих, предложив сельскому совету сдать здание и культовое имущество согласно имеющейся описи в аренду. Когда окончательно закрыли храм, установить не удалось, но в 1935 г. в Старомайнском районе действовали только две церкви – Александро-Невская в Старой Майне и Знаменская в Волостниковке.
Одно из последних упоминаний о Николаевском храме содержится в протоколе заседания Старомайнского исполкома за 11 февраля 1952 г., на котором обсуждался вопрос о передаче здания бывшей церкви в с. Старая Грязнуха районному пункту «Заготзерно»: «Кирпичное здание бывшей церкви в селе Старая Грязнуха попадает в затопляемую зону, в связи со строительством Куйбышевской ГЭС и подлежит сносу. Учитывая большую потребность в строительных материалах Старомайнского пункта Заготзерно, складские помещения которого переносятся из затопляемой зоны… на новую площадку, исполком районного Совета депутатов трудящихся решает:
1. Передать кирпичное здание бывшей церкви в селе Старая Грязнуха, подлежащее сносу… Старомайнскому пункту Заготзерно для разборки и использования кирпича и щебня, как строительного материала, при переносе складских помещений из затопляемой зоны на новую площадку.2. Просить исполком ульяновского областного Совета депутатов трудящихся утвердить настоящее решение».
Но позднее, в августе 1953 г. районные власти решили с целью обеспечения Старомайнского участка треста «Ульяновсксельстрой» кирпичом для переноса и нового строительства зданий школ, медицинских, культурно-просветительных и других учреждений передать ему бывшее церковное здание в с. Старая Грязнуха для разборки на кирпич.
Построенному в 1906 г. Николаевскому храму было отмеряно всего лишь 49 лет, так как в 1955 г. его взорвали (по документу 1 августа), а в 1956 – 1957 гг. бывшее село затопило Куйбышевское водохранилище.
