Католицький Хрестовоздвиженський костел у Полтаві був закладений у 1852-му році, а завершено побудову його в 1859-му році. До того, богослужіння велися у найманих приміщеннях, зокрема в будинку училища садівництва поблизу Міського саду. На той час переважною більшістю католиків у Полтаві, ймовірно були поляки, але костел також могли відвідувати вихідці з Австро-Угорщини та південних німецьких князівств, які приїжджали торгувати в Полтаву, зокрема, на Іллінський ярмарок.
Первісно проєкт костелу передбачав романтизовану історичну архітектуру з впливом італійської неоготики. Натомість, реалізований варіант при збереженні попередньої об’ємно-просторової композиції зовнішньо вирішений у формах близьких до ренесансу, або навіть класицизму. Вхідний портал був обрамлений двома масивними колонами, які тримали невеликий але масивний трикутний фронтон. Бічні фасади мали великі аркові вікна з тонкими обрамленнями. Головний фасад увінчувався трикутним фронтоном із барельєфною композицією – трикутником з оком посередині, від якого йдуть промені. Інтер’єр костелу, судячи з креслень, мав вигляд базиліки, перекритої великими пологими хрестоподібними склепіннями. Костел мав орган.
Закритий радянською владою у 1936-му і зруйновний у 1937-му році, частково на його місці в 1938-му році зведено у формах постконструктивізму будівельний технікум. Зараз тут розташовано Полтавський базовий фаховий медичний коледж Полтавської обласної ради.