Церковное место в Коледино известно с XVI в. После польско-литовского разорения в источниках упоминается двухшатровая деревянная церковь во имя мученика Андрея Стратилата, а в 1657 г. еще одна церковь — во имя Святой Троицы с приделом в честь Казанской иконы Божией Матери.

В Отечественную войну 1812 г. настоятель церкви отец Иоанн Виноградскийй спас от неприятеля церковное здание, антиминс, богослужебные сосуды, предметы ризницы и церковную казну, за что получил бронзовый крест на Владимирской ленте.

В 1815 г. владелец усадьбы Р.Е.Татищев, внук русского историка В.Н.Татищева, начал строительство существующего каменного здания церкви. Завершилось оно в 1822 г. при его дочери, Елизавете Ростиславовне, в замужестве княгини Вяземской. Проект создал Д.И.Жилярди с участием в Ф.М.Шестакова или А.Г.Григорьева. Здание построено в стиле русского классицизма, изысканных пропорций, однокупольное, соединено колоннами с отдельно стоящей двухъярусной колокольней, украшено белокаменной колоннадой с дорическими портиками, арочной впадиной, полуциркульными окнами, маленькой изящной главкой. Отопление проходило под полом по лабиринту тепловодов.

В 1930 г. храм закрыли. На протяжении 60 лет в нем находились сельхозсклад, квартиры, во время Великой Отечественной войны был снесен ярус колокольни, в окнах и стенах пробиты амбразуры для ведения оборонительных действий.

В 1990 г. храм возвратили верующим в плачевном состоянии. С ноября 1990 г. возобновлены регулярные богослужения. В настоящее время реставрация храма закончена, построено здание крестильни. При храме существует церковная библиотека, работает воскресная школа.