Gród na prawym brzegu rzeki Worskli (lewego dopływu Dniepru), pierwszy raz wzmiankowany (1174) jako Łtawa.

Pod koniec XIII w. zniszczona przez najazd Tatarów, w drugiej połowie XIV wieku przyłąćzona przez Olgierda do Wielkiego Księstwa Litewskiego.

12 sierpnia 1399 roku nieopodal Połtawy nad rzeką Worsklą doszło do bitwy pomiędzy wojskami litewsko-ruskimi (posiłkowanymi przez oddziały krzyżackie i polskie) wielkiego księcia Witolda, a wojskami tatarskimi, dowodzonymi przez murzę Edygeja. W zakończonej klęską Witolda bitwie zginęło kilkunastu Giedyminowiczów, kniaziów litewskich i wielu rycerzy polskich, wśród nich wojewoda krakowski Spytek z Melsztyna.

Połtawa wielokrotnie jeszcze była atakowana przez Tatarów (ostatni raz w 1695 roku).

Pod obecnę nazwą pojawia się (1430), gdy wraz z Litwą znajdowała się w granicach wspólnego państwa polsko-litewskiego.

Po zawarciu unii polsko-litewskiej w Lublinie (1569), Połtawa znalazła się w Koronie, należąc do starostwa perejesławskiego województwa kijowskiego. Wraz z okolicami stanowała posiadlośc ks. Jeremiego Wiśniowieckiego. Według inwentarza (1646) w okolicy istniało ponad 800 gospodaratw.

W maju 1648 po klęskach polskich pod Żółtymi Wodami i Korsuniem Połtawa została zajęta przez oddziały kozackie Bohdana Chmielnickiego. Do Rzeczpospolitej już nie powróciła.

W wojskowej administracji kozackiej stały się centrum pułku kozackiego. Jego dowódca, pułkownik kozacki Marcin Puszkar stanął na czele rebelii przeciw zawartej w Hadziaczu (1658) nowej ugodzie Rzeczpospolitej z Kozakami. Wiosną 1658 roku zajął m.in. Połtawę i Zinków.

Po zawarciu umowy perejesławskiej (1654) przyłączającej Ukrainę do Rosji zajęta przez wojska moskiewskie, co zostało przez Polskę uznane - czasowo w rozejmie andruszowskim (1667) i ostatecznie w pokoju Grzymułtowskiego (1686).

27 czerwca 1709 roku pod Połtawą armia krola Szwecji Karola XII, sprzymierzona z wojskami kozackimi Iwana Mazepy doznały klęski w bitwie z wojskami rosyjskimi cara Piotra I Wielkiego. Straty Szwedów wyniosły 9 tys. ludzi, stracili oni wielu dowódców ( ks. Lunemburski, Lennartson), ledwo z życiem uszedł król szwedzki Karol XII.

Bitwa miała też decydujące znaczenie dla Rzeczypospolitej, która formalnie w wojnie północnej (1700-21) nie uczestniczyła (brał w niej udział król Polski August II, jako elektor saski). Zadecydowała ostatecznie o mocarstwowej pozycji Rosji w tej części Europy i zakończyła erę dominacji Szwecji.

Od 1991 miasto obwodowe Ukrainy, liczy ponad 320 tys. mieszkańców