История храма восходит к концу XVI века. В 1596 году в селе Львово-Андреевском на реке Протве уже существовала деревянная церковь, построенная «клецки», во имя святого мученика Андрея Стратилата. После Смутного времени, в 1629 году, эта церковь стояла «без пения», то есть без совершения служб, и «в ней всякое церковное строение было мирское». На церковной земле тогда насчитывалось девять мест дворовых, принадлежавших церковным служителям и нищим, которые питались от церкви Божией.
В 1678 году, по ходатайству прихожан, была построена новая деревянная церковь во имя святого Андрея Стратилата. В 1715 году упоминается священник Алексей Демидов и его брат дьячек Гаврила, служившие в этой церкви. После секуляризации церковных земель в 1764 году село Андреевское перешло в ведение Коллегии Экономии.
В 1848 году, во время эпидемии холеры, в Андреевский приход приносили чудотворную Колочскую икону Божией Матери из Колочского монастыря Гжатского уезда Смоленской губернии. После этого в храме был установлен список этой иконы, а в 1874 году, при строительстве каменной церкви с колокольней, в трапезной был устроен придел в честь Колочской иконы Божией Матери.
Ныне существующий кирпичный храм в псевдорусском стиле был построен в 1874–1880 годах на средства прихожан. Двухсветный четверик церкви перекрыт сомкнутым сводом, на котором установлена декоративная главка. С востока к храму примыкает полукруглый алтарь, с запада — трапезная и трёхъярусная колокольня, перекрытая низким шатром с главкой. Декоративное убранство здания сдержанное, включает широкие лопатки, простые оконные наличники и карнизы с зубчиками; более богат декор колокольни. Главный престол посвящён святому Андрею Стратилату, в трапезной расположены приделы Колочской иконы Божией Матери и Всех Святых.
В середине 1930-х годов церковь была закрыта, здание разграблено и осквернено. В разные годы в нём размещались столовая, пивной бар, склад и котельная. К 1990-м годам храм находился в аварийном состоянии: стены отсырели, появились трещины, разрушились своды.
В начале 2000-х годов полуразрушенное здание было передано Русской Православной Церкви. На средства образовавшегося прихода начались реставрационные работы. В настоящее время в храме проводятся редкие богослужения.
