В 1863 году в казачей станице Егерухаевской (впоследствии переименованной в Тульскую) был открыт молитвенный дом, но размещался он в неприспособленном помещении, поэтому начинается строительство из дубового леса нового здания церкви, в самом центре станицы. В 1868 году постройка станичной церкви была завершена. В этом же году церковь во имя Святителя Николая была торжественно освящена при большом стечении народа. Перезвон ее колоколов радостно разнесся по долине реки Белой.
Стоимость здания церкви с иконостасом составила 20 тысяч рублей. 9 тысяч из них были выделены Кубанским войсковым правлением, остальные деньги были собраны прихожанами. Для священника станичным обществом был построен дом, состоящий из 3-х комнат. Позднее была построена церковная сторожка.
На 1898 год священником Никольской церкви станицы Тульской был Никольский Петр Алексеевич. В следующем году на этом посту его сменил выпускник Ставропольской духовной семинарии Покровский Викторин Евграфович, остававшийся в этой должности до момента закрытия церкви в 1925 году. Диаконом служил в это время Юрганов Александр Васильевич.
В станице имелась церковно-приходская школа, построенная станичным обществом за 2500 рублей, располагалась она на территории церкви. Обучались в ней дети казаков и иногородних. Заведующим школой был станичный священник. Школе принадлежал участок земли площадью 12 десятин. Обучение продолжалось в течение 3-х лет, а по успешном окончании курса ученику выдавалось свидетельство. Священником Покровским была приобретена и приведена в надлежащий вид учительская библиотека.
Осенью 1910 года был организован церковный хор станицы. Организатором и регентом хора являлся заведующий Тульским станичным училищем Федор Иванович Павлей. Хор состоял из детей казаков и взрослых мужчин.
В 1920 году церковно-приходская школа в станице была закрыта.
В 1922 году на основании декрета ВЦИК представителями власти были изъяты все церковные ценности. Богослужения в церкви были прекращены по запрету властей. Никольская церковь станицы Тульской была до основания разрушена в 1936 году.
В 1992 году на сходе граждан станицы было принято решение об открытии прихода , с чем и обратились в Управление Майкопской и Армавирской епархии с просьбой прислать священника. В этом же году в станицу назначается настоятелем прихода священник Александр Мекешкин.
Для совершения Богослужений приходу, местной администрацией, на правах безвозмездного пользования, без заключения договора, передается здание бывшего детсада. Строения находились в неудовлетворительном состоянии, но трудами станичников, в течении полугода, молельный дом стал уютным и готовым принимать в своих стенах православный народ.
С 2002 года на приходе послушание несет протоиерей Анатолий Александрович Старцев, также являясь благочинным Тульского округа. При нем начато строительство храма на месте разрушенного, часовни на территории районной больницы и открыта воскресная школа в которой занимаются 35 деток. Ведется подготовка документов для оформления права собственности на молитвенное здание и прилегающую к нему территорию, через суд, т.к. документов на собственность данных строений в архивах не нашлось.
В 2009 году приход приобрел звонницу из 7-ми колоколов, звон которых разливаясь над станицей зовет всех жителей станицы к Богу.
Источник: сайт Майкопской и Адыгейской епрахии
