Клуб был создан в 2011 году, бывшим футболистом Владимиром Сысенко (который стал главным тренером команды) и спортивным журналистом Станиславом Майзусом. Тогда же команда впервые приняла участие в чемпионате Полтавской области, а в 2014 впервые стала чемпионом Полтавщины, однако после этого клуб был расформирован, в связи с отсутствием финансирования. В 2019 году был найден новый спонсор в лице руководителя строительной фирмы и депутата Полтавского горсовета Сергея Иващенко и команда восстановила выступления[1]. В сезоне 2019/20 «Полтава» впервые приняла участие в любительском кубке Украины, а в следующем — в любительском чемпионате. В 2021 году клуб прошёл аттестацию для участия во второй лиге чемпионата Украины. Дебютную игру на профессиональном уровне «Полтава» провела 25 июля 2021 года, на домашнем стадионе победив «Сумы» со счётом 3:0. Первый гол команды в профессиональных соревнованиях забил Максим Горжуй[2].