1608 року великий коронний гетьман Станіслав Жолкевський заснував фортецю в Полтаві, яка була тоді „пустою слободою" на правому високому березі Ворскли, на межі Дикого Поля. Земляними валами, ровом і частоколом укріпили трикутний у плані мис, щонині зберігся в середмісті й називається Городищем. Він лежить між двома ярами - Мазурівкою і Панянкою. Під час археологічних розкопів тут виявлено рештки поселень скіфської доби (II ст. до н.е.), роменської культури (VIII ст.), великокнязівських часів (Х-ХІІ ст.).
За військово-топографічними умовами Городище було найвигіднішим місцем для фортеці. Дуже круті східні й південні схили його укріпили частоколом, а з напільного північно-західного боку (по трасі теперішньої пл. Леніна) викопали рів і насипали вал. З півдня фортецю омивала маленька річка Полтавка, що витікала з Мазурівки. Істотною вадою первісної фортеці була відсутність на її території джерела води. Тому у 40-х роках XVII століття під орудою коронного гетьмана Станіслава Конецпольського фортецю розширили майже вдвічі, включивши до її складу Мазурівку й частину плато на південний захід від неї. Відповідно і виникли назви фортеці - Стара (первісна частина) і Нова Полтава.
Первісні укріплення були дуже архаїчні - у вигляді невеликих земляних бастіонів напівкруглої та простокутної форми в плані, сполучених валами. На розі, приблизно там, де нині стоїть так звана Ротонда дружби народів, був великий, підковоподібного плану бастіон. Певно, найважливіші ділянки оборони посилювалися рубленими дерев'яними баштами. В'їзна брама містилася з північного заходу.
Після Переяславської угоди 1654 року Полтавській фортеці надавалося великого значення, тож 1658 року під орудою полтавського полковника Мартина Пушкаря її ремонтували. Для цього спеціально присилали з Москви воєводу А.Чиркова. Влітку того ж таки року Полтаву здобули штурмом і спалили війська повсталого проти Москви гетьмана Івана Виговського. Після того з наказу московського уряду фортецю відбудували, з'явився зовнішній пояс оборони: для захисту форштадта (передмістя) викопано рів і насипано вал, що перекрили рівнину між вершинами ярів Койкового та Кобищани.
1709 року, на час облоги Полтави українською і шведською союзними арміями, фортеця вже мала досить розвинену систему укріплень, близьку до бастіонної - у вигляді неправильного полігона, дещо витягнутого з півдня на північ. Було п'ять в'їзних брам: Подільська, Мазурівська, Київська, Спаська, Криловська. Лінія оборони складалася з сухого рову й крутого земляного валу з палісадом, але без валганга, „за козацьким звичаєм". Від наріжного підковоподібного східного бастіону вниз по рельєфу було винесено квадратовий у плані редут; від північного наріжного бастіону в бік Бойкового яру - так само. Укріплення між згаданими бастіонами складалися зі старого частоколу, без валу й рову, оскільки крутосхили були практично неприступні. На цій ділянці містилася Криловська брама, від неї вниз, на Поділ, спускалася стежка. Північний фронт укріплень мав два в'їзних вузли - Спаську й Київську брами, досить складні інженерні споруди: перед першою був равелін, друга становила горнверк з равеліном.
Уздовж схилів Мазурівського яру 1709 року ще зберігалися рештки первісних укріплень Старої Полтави 1608 року. Оборонці Полтави 1709 року поновили цю лінію оборони, передбачаючи можливість прориву шведами зовнішньої лінії оборони.
Від верщини Мазурівки, приблизно звідти, де нині стоїть пам'ятник В.Леніну, головна лінія оборони ламаним фронтом ішла на південь трасою теперішнього Першотравневого проспекта. Тут були Басманівська й Мазурівська глухі дерев'яні вежі, а також в'їзний вузол у вигляді великого горнверка, з вихідних гострих кутів якого можна було обстрілювати підступи до брами. Саме цю лінію укріплень нещадно штурмували під час шведської облоги, використовуючи всі здобутки й хитрощі європейського військово-інженерного мистецтва - міни, підкопи тощо.
Звідси головний вал ішов рівнобіжно до яру й від південного наріжного бастіону спускався вділ, перекриваючи Мазурівський яр і підходячи до підніжжя підковоподібного бастіону. На цій ділянці були Подільська брама та Глуха башта. Лінія укріплень одночасно правила й за греблю, яка перегачувала р.Полтавку, утворюючи у фортеці став - джерело води на час облоги.
Усі вежі були дерев'яні, рублені, чотиригранні, невисокі з наметовими дахами.
Полтавська фортеця вже на початку XVIII століття не відповідала європейському рівню фортифікації. Не випадково Петро І, оглядаючи, її після Полтавської битви, сказав полоненому фельдмаршалові Реншильду: „Дивно, що за такої тривалої облоги ви не змогли опанувати цю слабку фортецю".
Під час облоги укріплення було значно поруйновано, особливо його західний фронт, тому цар наказав реконструювати фортецю. Наказ не було виконано: 1723 року комендант полковник Чичерін доповідав Військовій колегії, що „Полтавської фортеці городові всі стіни опали..." 1724 року сюди для інспектування відрядили інженер-майора Деколонга, який оглянув фортецю і склав кресленика та кошториса на реконструкцію її. Після цих робіт трасування оборонних ліній істотно не змінилося, за винятком південної дільниці, де в'їзний вузол значно спростили: замість горнверка з'явився трикутний у плані равелін з брамою і баштою, що збереглася з давніх часів. Біля Київської брами горнверк з равеліном взагалі ліквідували, натомість зробили бастіон регулярних обрисів. Перед Спаською брамою було знищено равелін, і вона опинилася просто посеред валу. Північний бастіон перероблено з квадратового на п'ятикутний, такої зміни зазнав і підковоподібний східний бастіон. Внутрішню лінію укріплень вздовж Мазурівки після 1722 року ліквідували.
1730 року реконструйована фортеця мала високі земляні вали з частоколом, земляні бастіони більш-менш регулярних обрисів, сухий рів і 8 башт, що збереглися з попереднього періоду, причому деякі з них були напівзруйновані: Криловська, Спаська, Київська, Басманівська, Мазурівська. Глуха та дві безіменні.
У такому вигляді фортеця проіснувала, поступово руйнуючись, до 1805 року, коли вали й рови прорізали новорозпланованими вулицями. 1817 року, за розпорядженням генерал-губернатора, вали розкопали, рови засипали і на місці їх проклали бульвари.
У сучасній містобудівній структурі фортеця виділена розпланувальне й композиційне. Трасами валів пролягають Першотравневий проспект, частково вулиці Леніна та Панянка. Фортечній еспланаді відповідає сквер на пл. Леніна. Найдавніша частина фортеці - Городище або Стара Полтава - розміщена на високій горі і нині є визначною ландшафтною домінантою в панорамі міста.