В 1745 году княжна Мария Кантемир приобрела сельцо Улитино у Ивана Ивановича Вельяминова-Зернова. В то время в сельце насчитывалось 13 крестьянских дворов, и оно относилось к приходу церкви Николая Чудотворца в селе Гребнево, расположенном в четырех верстах. Из-за трудностей, связанных с посещением удаленного храма, особенно в весенний и осенний периоды, княжна Кантемир обратилась в Московскую духовную консисторию с прошением о строительстве собственной церкви в Улитино. 2 июля 1746 года ей было выдано разрешение на строительство каменного храма во имя святой равноапостольной Марии Магдалины.
Строительство церкви было завершено в 1748 году, о чем свидетельствует выдача антиминса архиепископом Гавриилом 30 сентября того же года. Храм представлял собой небольшой каменный четверик с одной апсидой под высоким купольным сводом, выполненный в стиле барокко. Интересно отметить, что освящение храма в честь святой Марии Магдалины было редкостью для того времени.
В период с 1835 по 1842 годы храм был значительно расширен и украшен. Под руководством священника Андрея Николаевича Соколова, выпускника Московской духовной семинарии, к существующему объему церкви была пристроена обширная трапезная с двумя приделами и колокольня. Правый придел был освящен во имя иконы Божией Матери «Всех скорбящих Радость» в 1842 году, а левый — в честь святителя Николая Чудотворца — несколько позднее. Колокольня имела три яруса и была оснащена восемью колоколами, самый большой из которых весил 312 пудов.
После революции 1917 года храм пережил тяжелые времена. В 1934 году он был закрыт, кресты с куполов и колокольни были сняты, а в 1960-х годах трапезная и колокольня были полностью снесены. Оставшийся четверик использовался для различных нужд: в нем размещались клуб, кинотеатр, а затем магазин.
Восстановление церковной жизни в Улиткино началось в 1997 году. В октябре того же года в храм был назначен настоятель, и начались регулярные богослужения. 24 апреля 1999 года в храм была возвращена главная святыня — икона святой Марии Магдалины, которая долгие годы находилась в соседнем храме в селе Гребнево.
Архитектурно храм представляет собой четверик с одной апсидой под высоким купольным сводом. Первоначально выполненный в стиле барокко, после восстановительных работ храм сохранил основные черты своего исторического облика. Внутреннее убранство храма было богато украшено деревянной резьбой, однако значительная часть декора была утрачена в годы запустения.
В настоящее время Магдалининский храм является действующим и относится к Балашихинской епархии Русской Православной Церкви. Богослужения совершаются регулярно в выходные и праздничные дни. При храме действует воскресная школа для детей, организуются приходские праздники, посвященные основным православным торжествам.
