Всесвятская кладбищенская церковь, по Кобелякской улице, каменная о пяти главах, с колокольней в одной с ней связи, начата постройкой 29 июня 1858, окончена и освящена 18 октября 1864 г. Постройка ее произведена при главном участии управлявшего в то время здешней палатой государственных имуществ генерал-майора Григория Васильевича Яковлева. Постройка церкви обошлась в 15402 р. 81 к.

До построения этой церкви на этом же кладбище, но в другом месте существовала тоже деревянная церковь, перенесенная сюда в 1808 г. иждивением приказа общественного призрения со старого кладбища, бывшего в ХVIII столетии в той местности, где теперь новый базар, и построенная там в 1740 году. На новом месте она была исправлена в 1852 году.

Церковь эта в 1865 году продана на снос в с. Кустолово, Кобелякского уезда. Причта при церкви не было, а попеременно она находилась в заведовании то Полтавского Крестовоздвиженского монастыря, то Успенского собора; с 1862 г. состоит самостоятельной.

Престолов три: главный во имя Всех Святых, придельные — с правой стороны — во имя св. и праведной Елисаветы (5 сентября), освящен 27 апреля 1865 года, с левой — во имя св. кн. Ольги (11 июля), освящен 25 ноября 1890 года. Под церковью находится погребальный склеп. Новое кладбище открыто 1 сентября 1872 года.

При этой церкви 12 января 1897 года открыто братство во имя Пресвятой Богородицы.

Бучневич В. Е. Записки о Полтаве и ее памятниках.
2-е изд. Исправл. и дополн. Полтава. 1902 г. Стр. 251-252