Создание церкви в Берендеево, как и ряда других церквей в России, было связано с железнодорожной катастрофой 1888 года на Курско-Харьковской железной дороге у станции Борки, в которой чудом не пострадали император Александр III и его семья. В память об этом событии 17 апреля 1889 года настоятельница Федоровского монастыря в Переславле, игуменья Евгения, установила на станции икону Федора Стратилата. Эта энергичная монахиня активно участвовала не только в обустройстве Федоровского монастыря, но и в распространении монашества за его пределами, включая организацию еще двух пустыней: Воскресенской в селе Новоселье и Алексеевской в селе Новоалексеевка. В результате ее деятельности было создано три пустыни, четыре церковно-приходские школы, монастырь, который давал приют более 400 монахиням и послушницам и воспитывал несколько девочек-сирот. При монастыре были организованы хоры певчих. На момент национализации монастырю принадлежало 1016 десятин и 957 сажен земли. В ответ на просьбу игуменьи Евгении о строительстве часовни при станции Берендеево, 30 апреля 1890 года Владимирская Духовная консистория выдала указ, и 6 августа 1890 года была заложена каменная часовня. Земли для строительства часовни пожертвовали крестьяне деревни Ростино.

2 октября 1892 года священник из церкви села Давыдово Петр Аматов освятил и установил крест на часовне в присутствии генерала Гавриила Самсонова, одного из благотворителей. 30 мая 1893 года архимандрит Модест освятил часовню в присутствии сестер Федоровского монастыря и духовенства. В 1895-1897 годах, благодаря поддержке М.П. Глинской, часовня была перестроена в церковь. Близ станции Берендеево была создана пустынка, для которой московский купец Василий Рыбаков пожертвовал 5 десятин земли. Пустынь обнесли каменной стеной, а для содержания священника был выделен особый капитал. В 1898 году на средства монастыря и московских благотворителей были построены два деревянных дома для монахинь и послушниц, каменный дом для священника и каменный дом для церковно-приходской школы. Большинство строений Берендеевой пустыни сохранились до наших дней. Первым настоятелем церкви Всех Святых стал протоирей К.И. Покровский из Федоровского монастыря. Под его руководством 1 сентября 1898 года начались занятия в церковно-приходской школе при пустыни Всех Святых. В церкви проживало до 80 человек, включая 22 девочки-сироты. Насельницы занимались хлебопечением, рукоделием и сельским хозяйством на землях села Петровское, пожертвованных церкви А.М. Ушаковым.

В 1918 году, согласно декрету об отделении церкви от государства, церковно-приходская школа при Всехсвятской пустыни была передана уездному комитету народного образования. В 1923 году пустынь была закрыта, а церковь стала приходской. В 1929 году церковь была закрыта по постановлению президиума Владимирского исполнительного комитета, а здание передано под клуб Берендеевского торфопредприятия. В 1990 году церковь была возвращена верующим, и началось ее восстановление.