Основание часовни
Поводом к созданию церкви в Берендеево, как и нескольких других церквей в России, стала железнодорожная катастрофа 1888 г. на Курско-Харьковской железной дороге у станции Борки, в которой августейшая семья и император Александр III чудом не пострадали. В память об этом событии 17 апреля 1889 г. игумения Евгения (Георгиевская), настоятельница Федоровского монастыря г. Переславля, принесла и установила на станции икону с изображением великомученика Феодора Стратилата.
По прошению игумении Евгении о разрешении строительства часовни при станции Берендеево 30 апреля 1890 г. последовал указ Владимирской духовной консистории, а 6 августа 1890 г. состоялась закладка каменной часовни. Землю для строительства пожертвовали крестьяне дер. Ростино.
От часовни к храму и пустыни
2 октября 1892 г. священник церкви села Давыдово Пётр Аматов освятил и водрузил на предназначенное место крест. Это происходило в присутствии одного из благотворителей, генерала Гавриила Самсонова. 30 мая 1893 г. архимандрит Модест в присутствии сестер Федоровского монастыря и духовенства освятил часовню.
В 1895–1897 гг. при благотворительной поддержке М.П. Глинской часовня была перестроена в церковь. Близ станции Берендеево устроили пустынку, для которой московский купец Василий Рыбаков пожертвовал 5 десятин земли. Пустынь обнесли каменной стеной, а на содержание священника был вложен особый капитал.
В 1898 г. игумения Евгения на монастырские средства и, в большей степени, на средства московских благотворителей построила два деревянных дома для монашествующих и послушниц, каменный дом со всеми хозяйственными службами для священника и каменный дом для церковно-приходской школы. Почти все строения Берендеевой пустыни дошли до наших дней. Первым настоятелем церкви Всех святых стал священник Федоровского монастыря, протоиерей Константин Иванович Покровский. Под его руководством 1 сентября 1898 г. начались занятия в церковно-приходской школе при пустыни Всех святых.
При церкви Всех святых проживало до 80 человек, в том числе 22 девочки-сироты. Насельницы пекли хлеб, занимались рукоделием и сельским хозяйством на землях села Петровское, пожертвованных церкви потомственным почетным петроградским гражданином Авраамием Михайловичем Ушаковым.
Закрытие, утрата и возвращение
В 1918 г., после декрета об отделении Церкви от государства, церковно-приходская школа при Всехсвятской пустыни была отобрана у монастыря и передана в ведение уездного комитета народного образования. В 1923 г. пустынь закрыли, а церковь при ней стала приходской. В 1929 г., по постановлению президиума Владимирского исполнительного комитета, церковь закрыли, а её здание передали под клуб Берендеевского торфопредприятия. В советское время на берендеевых болотах добывали торф.
В 1990 г. церковь была возвращена верующим, после чего началось её восстановление.