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