Ця церква вважаться однією з найстаріших у Полтаві. Перші записи про неї було знайдено серед документів Полтавського козацького полку, датованих 1686 роком. Можливо, вона була боковим приділом Преображенської церкви, що згоріла 1705 року. Священик Іван Світайло відбудував приділ згорілої церкви з матеріалу розібраного в Хрестовоздвиженському монастирі дерев'яного храму. За легендою цар Петро I молився в Спаській церкві після перемоги над армією Карла XII у Полтавській битві 27 червня 1709 року. Багато дослідників Полтавської битви вважають, що саме біля Спаської церкви були поховані захисники фортеці Полтава.
  В 1811 році Преображенська церква була остаточно розібрана через її ветхість. Зберігся тільки боковий придiл, як згадка про її роль в історії Російської Імперії. Старший син імператора Миколи I Олександр (майбутній цар Олександр II ) відвідав Полтаву в 1837 році, оглянув церкву, яка на той час знаходилася у дуже занедбаному стані, і пожертвував 2000 рублів на її ремонт. Пізніше дворяни Полтавської губернії зібрали ще близько 25000 рублів приватних внесків. На ці кошти в 1845 році над церквою, за проектом академіка архітектури Андрія Тона спорудили цегляне шатро. Дещо пізніше, в 1847 році біля церкви побудували та освятили дзвіницю. Впродовж 1875 - 1898 років Спаська церква була полковою церквою 33-го піхотного полку, що на той час дислокувався в Полтаві. В 1890 році було закінчено спорудження навколо храму кам'яної огорожі з кованими решітками. В 1902 році було проведено капітальний ремонт Спаської церкви. Після перемоги більшовицької революції 1917 року Спаська церква, на щастя, не була ані закрита, ані зруйнована і продовжила функціонувати аж до початку 30-х років. Втім на початку 30-х років вона була зачинена через заборону богослужінь з боку радянської влади. Тоді ж розібрали і церковну дзвіницю. Німецька окупаційна влада дозволила правити службу в храмі впродовж 1941-1943 років. В 60-і роки була демонтована огорожа церкви і знищені могили храмового кладовища. У 2009 році була відбудована дзвіниця храму у її первісному вигляді. Інша дзвіниця, зведена на початку XXI ст. тепер використовується як каплиця.