Футбольний клуб «Полтава» - одна з наймолодших команд у професійному українському футболі. Вона була заснована 25.06.2007 р рішенням сесії Полтавської міської Ради. Команда створена під патронатом мера міста А.В. Матковського, який є Почесним Президентом клубу, і Леоніда Соболєва, який став головним спонсором і Президентом клубу. В кінці 2011 р Полтавська міськрада за погодженням вийшов зі складу засновників.
Таким чином, представник еліти «Ворскла» отримала «молодшого брата». Однією з пріоритетних завдань клубу була підготовка футболістів для команд першої та вищої ліг. І хто знає, можливо в недалекому майбутньому два полтавських клубу будуть всерйоз конкурувати між собою, як це було півстоліття тому, коли повні трибуни стадіонів збирали матчі місцевих «Колгоспника» і «Локомотива».
Клуб має договір про співпрацю з футбольної ДЮСШ імені І.І. Горпинко міського відділу освіти.
Домашні матчі команда проводить на стадіоні «Локомотив», який знаходиться в старовинному районі міста - на Подолі. Стадіон був повністю реконструйований (2500 індивідуальних пластикових крісел, в 2008р. Введена в експлуатацію VIP-трибуна для почесних гостей). Реконструкцію профінансував президент клубу Леонід Соболєв.
Також футбольний клуб «Полтава» отримав сучасну спортбазу, яка знаходиться за адресою: провулок Шевченка, 20а. Будівля бази перетворено в даний житло для футболістів із затишними кімнатами, сауною, тренажерним залом.
І якщо в першому своєму сезоні "Полтава" не входила в число лідерів групи "Б" другої ліги, то в наступні роки команда постійно боролася за перемогу в турнірі. Кілька років поспіль полтавці були близькі, але не вистачало буквально чуть чуть. Сезон 08/09 - 2-е місце і стиковий матч за вихід в 1-ї ліги, в якому полтавчани поступаються 0-1 білоцерківському "Арсеналу". Потім першість 2009/10 - 3-е місце, в в чемпіонаті 2010/11 знову 2-і. І знову поразка в матчі плей-офф від "Сум". Щоб більше не спокушати долю в сезоні 2011/12 було поставлено завдання - 1-е місце і вихід в першу лігу. Що команда і виконала. І в сезоні 2012/13 р дебютувала в першій лізі.
В цьому ж році "Полтава" отримала можливість готуватися до матчів на тренувальних полях (одне натуральне, одне штучне), які були введені в експлуатацію на заміській базі. Там же закінчується будівництво житлового корпусу на 100 місць, де будуть створені всі необхідні умови для проживання і підготовки ігор.
За підсумками сезону 2017/2018 у Першій лізі України «Полтава» зайняла 2 місце, що дозволило їй брати участь в плей-офф за вихід в Прем'єр-лігу. Суперником команди став одеський «Чорноморець». 23 травня 2018 року в першому матчі в Одесі була зафіксована мінімальна перемога господарів. Але через 4 дня «городяни» святкували розгромну перемогу 3: 0, завдяки якій полтавчани вперше в своїй історії вийшли в еліту українського футболу.