Poltava fästning med dess jordvallar, diken och pålverk byggdes 1609 av kosacker från Mirgorod regemente, under befäl av den polske kosackhövdingen Stanislav Jolkevsky. Placerat på toppen av en höjd med utsikt över Vorsklas västra flodbank var fästningen huvudsakligen skyddad av de omgivande branta sluttningarna mot öst, syd och norr. I mitten av 1600-talet blev fästningen hemvist för Poltava kosackregemente. Regementet spelade en strategisk roll inom systemet med de försvarsinstallationer som upprättades i Ukraina för att skydda regionen mot invasion från Baty-Khan. Snart efter undertecknandet av Pereyaslavfördraget blev fästningen delvis återuppförd under ledning av moskvabon voevode Chirkov. Vid tiden för det svenska anfallet 1709 var fästningen omgiven av raviner, skyddad av pålverk/palissader och hade många bastioner samt fem öppningar skyddade av specialtorn för att trygga anslutande vägar till fästningen. Jämfört med några andra fästningar vid denna tid hade den dock stora brister. Kvällen före slaget informerades tsar Peter om att kosackhövdingen Mazepa var i den svenske kungens läger. Han beordrade då att fästningens kommendant överste Levenets, vän till Mazepa, skulle placeras i husarrest i Kharkov och ersättas av överste Kelin. Tre infanteribataljoner tillfördes fästningen som förstärkning.
    En av många vanliga myter bland först ryska och sedan sovjetiska historiker är den om "heroiskt försvar av fästningen i april - maj 1709". I Poltava finns ett monument över kommendant Kelins "modiga försvar av Poltavafästningen", vilket avtäcktes 1909 i närvaro av tsar Nikolaus II. I verkligheten förekom inget försök att inta fästningen. Svenskarna hade belägrat det med enda syfte att tvinga Peter I att engagera sig i ett avgörande slag.
    Löjtnanten vid Dalaregementet, Robert Petre, som under belägringen förde befälet över en pluton grupperad i löpgravar nära fästningens östra del, efterlämnade en dagbok som publicerats i Sverige. Ett intressant avsnitt handlar om ett samtal avlyssnat av löjtnanten mellan Karl XII och chefen för belägringsartilleriet, överste von Binau. Översten ville få tillåtelse att med beskjutning förstöra fästningen på sex timmar, men nekades detta. Petre drog därav slutsatsen att kungens syfte med belägringen var att "probera om fienden ville hålla stånd och staden försvara", något som "Hans Maj:t aldrig kunnat honom bringa sedan Holofzin" (1708). Det är ju också svårt att tro att den erfarna svenska armén var oförmögen att inta den primitiva försvarsinstallationen, som bara hade fem kanoner och ej var byggd av sten.
    Fästningen reparerades sista gången i slutet på 1720-talet. Efter undertecknandet av rysk-turkiska fredsfördraget 1744 flyttades gränsen för det ryska kejsardömet ytterligare söderut och Poltavafästningen började förlora sin betydelse. Vid den tiden hade Moskva börjat använda beteckningen "Lilla Ryssland" för Ukraina.
    På 1800-talet, när Poltava blev central stad i Malorossiyskaya (Lilla Rysslands) styrelse, bröt nya gator på många ställen genom fästningens försvarsverk. Då tsar Alexander I besökte Poltava 1817, var fästningen raserad till grunden. Detta väckte hans stora missnöje eftersom det ryska kejsardömet vid denna tid ville göra Poltava till en symbol för sin styrka.