История храма начинается с конца XVII века, когда в селе Павельцево существовала деревянная церковь. В 1682 году на её месте князь Иван Борисович Репнин начал строительство каменного храма во имя Спаса Нерукотворного Образа с приделом в честь преподобного Андрея Критского. Строительство было завершено в 1684 году.
Архитектурно храм представлял собой небольшой одноглавый бесстолпный четверик, перекрытый сомкнутым сводом, с северным приделом, связанным с основным объёмом обходной галереей. Такое архитектурное решение было характерно для того времени и отражало традиции русского церковного зодчества.
В 1730-х годах имение Спасское-Котово, где располагался храм, перешло во владение князей Юсуповых. При Борисе Григорьевиче Юсупове в северном приделе, ранее использовавшемся как ризница, был устроен престол и жертвенник, а также установлен иконостас. В июле 1755 года придел в честь Владимирской иконы Богородицы был освящён протопопом Большого Успенского собора.
Со второй половины XVIII века Спасская церковь стала родовой усыпальницей князей Юсуповых. В 1772 году в северном, Владимирском, приделе был устроен склеп, где была погребена Анна Борисовна Протасова, дочь Бориса Григорьевича Юсупова. В 1788 году рядом с ней была похоронена её мать, Ирина Михайловна Юсупова. Над их могилами были установлены чугунные надгробные плиты.
В 1820 году в склепе под полом храма была похоронена Параскева Павловна Юсупова, невестка князя Николая Борисовича Юсупова. Сам Николай Борисович, известный государственный деятель екатерининской эпохи, был похоронен в 1831 году за алтарём Владимирского придела. В 1832 году его сын, Борис Николаевич Юсупов, выстроил над могилой отца часовню-усыпальницу. Борис Николаевич скончался в 1849 году и был похоронен рядом с супругой Параскевой Павловной в склепе храма.
До 1850-х годов Спасская церковь имела только один придел — Владимирской иконы Богородицы. В 1850 году при Николае Борисовиче Юсупове, внуке одноимённого вельможи, был составлен проект южного придела в честь святителя Николая Чудотворца. Новый придел, освящённый в 1853 году, значительно расширил пространство храма.
В 1859 году Юсуповы устроили при храме богадельню во имя святой мученицы Татианы, а в 1863 году была создана церковно-приходская школа. В начале XX века стены храма были украшены росписью. Однако к этому времени имение начало приходить в запустение. Последним владельцем села Спасское-Котово был князь Феликс Феликсович Юсупов.
В 1934 году, в период советской власти, храм был закрыт. Здание подверглось разграблению и частичному разрушению: были уничтожены колокольня от яруса звона, купола, оконные украшения. Расположение окон и дверей было изменено. На месте усыпальницы была запущена угольная котельная. С южной стороны пристроено двухэтажное здание, помимо других построек на территории бывшего храма. В разные годы помещения церкви занимали спичечная и пуговичная фабрики, мыловаренная мастерская, областная типография.
С 1991 года усилиями верующих началось восстановление храма, несмотря на то, что на его территории ещё действовала типография. Первое богослужение состоялось 8 сентября 1991 года на праздник Владимирской иконы Божией Матери. Первые службы после 60 лет запустения проводились в Никольском приделе. Постепенно храм с пристройкой и территорией был полностью передан общине.
