Согласно писцовым книгам, в 1627 году в селе Коледино существовала деревянная церковь во имя мученика Андрея Стратилата. В 1657 году в селе уже значились две церкви — Андрея Стратилата и Святой Живоначальной Троицы с Казанским приделом.
В 1815 году началось строительство каменного храма во имя Живоначальной Троицы. Инициатором строительства выступил владелец усадьбы Ростислав Евграфович Татищев, внук известного русского историка В.Н. Татищева. Строительство завершилось в 1820 году, а освящение храма состоялось 9 августа 1822 года по благословению митрополита Московского и Коломенского Филарета (Дроздова).
Архитектура храма выполнена в стиле ампир. Проект приписывается архитектору Д.И. Жилярди, хотя есть предположения об участии других зодчих, таких как А.Г. Григорьев или Ф.М. Шестаков. Храм представляет собой однокупольное здание с равновеликими апсидальным алтарем и притвором, соединёнными с ним небольшой колоннадой двухъярусной колокольни. Колокольня обрамлена колоннами, поддерживающими дорические портики на первом ярусе; второй ярус повторяет первый, но с уменьшенными пропорциями и венчается четырёхгранной главкой.
В 1930 году храм был закрыт, и на протяжении более шестидесяти лет в нём находились сельскохозяйственный склад и жилые помещения. Во время Великой Отечественной войны здание храма было укреплено для обороны Москвы: снесён ярус колокольни, в окнах и стенах пробиты амбразуры.
В 1990 году храм был возвращён церковной общине, и с ноября этого же года в нём возобновились регулярные богослужения. В настоящее время реставрация храма окончена. Рядом с ним построено здание крестильни; при храме работает воскресная школа, имеется церковная библиотека. В храме находятся икона Божией Матери «Всецарица» и образ великомученика Пантелеимона, написанные на горе Афон. Также на территории храма возведён памятник защитникам Родины от немецко-фашистских захватчиков.
