Згідно переказів мати візантійського імператора Костянтина Великого свята рівноапостольна Олена віднайшла в IV столітті в Єрусалимі печеру, в якій розкопали три хреста і неподалік від них дошку з написом: "Ісус Назорей, Цар Іудейський". Щоб дізнатися, який з трьох – Хрест Спасителя, Єрусалимський патріарх Макарій став підносити їх по черзі до тяжкохворої жінки. Від двох хрестів ніякого дива не відбулося, коли ж поклали третій – жінка відразу одужала. В такий спосіб дізналися про справжній Чесний Хрест Спасителя. Того ж дня на цвинтар несли померлого і коли на труну поклали третій хрест – небіжчик ожив. Таким чином Господь показав Животворну силу Свого Хреста.
Згодом на місці хрестних страждань Ісуса Христа була зведена церква Гроба Господнього, а патріарх Макарій вперше запровадив свято виносу Хреста на подвір'я церкви та Воздвиження, тобто підняття його над головами віруючих. Це одне з великих свят Православної Церкви. У наші дні його відзначають щорічно 27 вересня, цей день – храмове свято Полтавської обителі.
Час заснування Хрестовоздвиженського монастиря – 1650 рік.
Засновник – ігумен Спасо-Преображенського монастиря (Лубни) Калістрат.
Ктитори: Мартин Пушкар, Іван Іскра, Іван Крамар.
Освячений: Київський митрополит Сильвестр Косів.
За переказами, які зафіксовані в історичних джерелах ХІХ - поч. ХХ ст., у монастирі була штаб-квартира шведського короля Карла ХІІ під час облоги Полтавської фортеці 1709 р.
У 1845 р. під час мандрівки Полтавщиною Тарас Шевченко виконав акварельний малюнок «Воздвиженський монастир у Полтаві».