Первое упоминание о крепости Полтава было найдено в плане, составленном французским военным инженером Гильйом-Левассер де Боплан, который в 1630-1647гг. занимался фортификационным строительством на Украине. В 1649 году Полтава стала административным центром созданного украинского казацкого полка, первым полковником которого был Мартин Пушкарь. Крепость играла значительную роль в системе оборонных укреплений, созданной для защиты от многочисленных орд, вторгавшихся в пределы Украины. Она стояла на возвышении правого берега Ворсклы, и со всех сторон, кроме северно-западной, была окружена крутыми склонами, которые спускались в долину, в то время сильно заболоченную многочисленными притоками Ворсклы.
    В 1658 году, вскоре после подписания Переяславского договора, крепость была частично реконструирована. Накануне Полтавской битвы крепость была расширена и состояла из двух частей, разделенных Мазуровским оврагом. На внешней линии обороны было построено 10 крепостных башен и 5 башен для охраны крепостных ворот. Земляные укрепления были усилены частоколом. В конце 1708 года комендантом крепости был назначен полковник Алексей Келин (Колен, Келен, Келинг (? -1715)), командир Тверского пехотного полка. Под его командованием полк принимал участие во многих сражений Северной войны: осаде Нотебурга (1702), Ниеншанца (1703), Дерпта и Нарвы (1704), а также взятии Быхова (1707). Гарнизон крепости Полтава накануне Полтавской битвы составлял 4182 человека.
    В конце апреля 1709 года шведская армия Карла XII подошла к Полтаве. Основные осадные траншеи находились с юго-западной стороны крепости. Военные действия сводились к рытью шведами подкопов и установке пороховых зарядов. Защитники крепости разоружали заряды и многочисленными вылазками наносили потери противнику. После Полтавской битвы осада крепости была снята, а остатки шведской армии отступили на юг к реке Днепр.
    В последний раз крепость реконструировали в конце 20-х годов XVIII ст. После подписания в 1774 году мирного договора с Турцией границы Российской империи передвинулись на юг и крепость потеряла свое стратегическое значение. Остатки крепостных укреплений были уничтожены в 1817 году, накануне визита царя Александра I в Полтаву.