СК Полтава був заснований 2011 року. Ідейними натхненниками створення клубу стали Володимир Сисенко та Станіслав Майзус. Основу колективу складали здебільшого вихованці місцевого футболу.
Свій перший матч в історії команда провела 13 квітня 2011 у рамках Кубка Полтавської області. Суперником СК Полтава стала полтавська Молодь, перший матч з якою завершився безгольовою нічиєю. Поступово полтавці зростали і крок за кроком рухалися до найвищого досягнення на обласному рівні. 2014 року СК Полтава став чемпіоном обласних змагань та володарем Суперкубка області. Після успішного сезону команда призупинила виступи.
А 2019 року почала писати нову сторінку в житті клубу. Це сталося завдяки приходу головного інвестора Сергія Іващенка, який вдихнув нове життя у клуб, після чого команда почала торувати шлях до нових висот з обласного рівня. Упродовж усього часу виступів на аматорському рівні колектив складався здебільшого з вихованців обласного футболу.
У цьому ж році полтавці дебютували на всеукраїнській арені, заявившись на Кубок України серед аматорських колективів. Дебют колективу під керівництвом незмінного тренера Володимира Сисенка був доволі вдалим. Уже в першому раунді полтавці за сумою двох ігор упевнено переграли LS Group із Сум. Загалом у цьому розіграші малиново-золоті дійшли до чвертьфіналу, де поступилися Таврії з Новотроїцького. На обласному рівні полтавцям не вистачило лише дещиці до потрапляння на п’єдестал.
Наступний сезон містяни знову почали з обласних змагань, де за підсумками сезону стали срібними призерами у чемпіонаті та фіналістами Кубка. А влітку 2020 року СК Полтава заявився на аматорський чемпіонат України, потрапивши до групи 3 (команди української першості були розділені на три групи за територіальним принципом). Дебютну зустріч містяни провели у Полтаві на стадіоні Локомотив проти запорізького Мотора. Перший історичний гол в аматорській першості забив Вадим Підлепич. Проте здобути позитивний результат нашим хлопцям не вдалося (1:4). Першу перемогу, до того ж розгромну, малиново-золоті здобули туром пізніше у виїзній грі проти кропивницької Зірки - 7:0.
За підсумками сезону у національній аматорській першості полтавці посіли 5 позицію в групі 3, хоча боротьба за вихід до раунду плей-оф точилася ледь не до останнього туру.
Улітку 2021 року СК Полтава отримав професіональний статус та дебютував у групі Б другої ліги. 25 липня полтавці провели першу гру в новому для себе чемпіонаті. Вдома містяни приймали іншого дебютанта ліги - ФК Суми. Матч завершився розгромною перемогою полтавців (3:0), а перший – історичний - гол на професіональному рівні за малиново-золотих забив Максим Горжуй.
Окрім яскравих перемог, були і неприємні поразки. Так, найбільшого розгрому у своїй історії містяни зазнали від херсонського Кристала 23 серпня 2021 ( 6:0).
У першому в історії професіональному сезоні містяни йшли стабільним середняком і навіть могли б краще завершити ігровий рік. Проте через початок повномасштабної війни росії проти України першість не була завершена. Футбольне життя зупинилося на кілька місяців. Однак уже навесні 2022 року, не знаючи, чи буде відновлений чемпіонат, полтавці розпочали підготовку та проводили тренування. Улітку стало відомо, що футбол в Україні таки буде. Але через війну чимало клубів призупинили діяльність. Щоб зберегти конкурентний чемпіонат у першій лізі, низка клубів другої ліги отримала запрошення для участі в першості. У їх когорті були і полтавці. Тому в сезоні 2022/23 на містян очікував черговий дебют, цього разу в першій лізі.
Наприкінці серпня 2022 року СК Полтава вдома мав приймати земляків з ФК Гірник-Спорт. Однак стартова гра сезону не відбулася через бюрократичні моменти. Тому першу свою гру в другому за рангом дивізіоні полтавці провели лише 3 вересня у Києві. Суперником стала столична Оболонь. Матч був сповнений драми, де містяни лише на останніх хвилинах поступилися - 2:1. Дебютний гол у першій лізі забив на 11 хвилині захисник Олександром Томенко. На першу звитягу у першій лізі довелося чекати аж до п’ятого туру, де містяни здобули переконливу перемогу в обласному дербі над кременчуцьким Кременем з рахунком 2:0.
Система проведення змагань у сезоні 2022/23 була відмінною від звичної колової. На першому етапі були сформовані дві групи по вісім команд за територіальним принципом. Змагання проводилися у два кола за коловою системою. На другому етапі команди, що посіли 1-4 місця в кожній групі, формували групу чемпіонська, яка боролася за вихід в УПЛ із збереженням очок, отриманих на першому етапі в іграх лише між собою. Команди, що посіли 5-8 місця в кожній групі, формували групу вибування, де боролися за збереження прописки зі збереженням очок, отриманих на першому етапі в іграх лише між собою. На другому етапі команди групи А проводили матчі тільки з командами групи Б у два кола.
Специфічний підхід до підрахунку очок на другому етапі відкинув полтавців у турнірній таблиці нижче за деякі клуби, які за підсумками першого етапу мали меншу кількість очок, ніж наш колектив. Тож полтавці були близькі до потрапляння в зону перехідних матчів. Але за два тури до кінця сезону все ж змогли убезпечити себе від стикових матчів.
Улітку 2023 року на СК Полтава чекало кадрове перезавантаження. Саме воно й стало відправною точкою для нових звершень. Під час міжсезоння Полтава стала прихистком для низки гравців ФК Скорук, який був вимушений призупинити виступи після ворожого підриву Каховської ГЕС. Сезон 2023/24 полтавці провели більш переконливо і не засмучували своїх уболівальників. За підсумками першого етапу СК Полтава гарантував місце у чемпіонській групі. Містяни гідно змагалися з конкурентами за підвищення в класі, проте посіли лише 8 сходинку за підсумками сезону.
Старт сезону 2024/25 був дуже потужним. Полтавці зберегли кістяк основної команди та здійснили точкове підсилення. Клуб розпочав сезон кубковим протистоянням з Тростянцем, перемігши 1:0 та вперше пробившись до другого раунду турніру. Але далі у драматичному матчі містяни поступилися Металісту 1925 у виснажливому 120-хвилинному протистоянні (5:3). І якщо в Кубкові удача відвернулася, то в календарній першості малиново-золоті продемонстрували феєрію: 9 матчів тривала безпрограшна серія, під час якої полтавці змогли переграти конкурента за лідерські позиції - Металіст 1925. Команда, на яку ще до сезону не ставив ніхто, крок за кроком рухалася спочатку до потрапляння у чемпіонську групу, а згодом, під час весняної частини сезону, і до історичного виходу в УПЛ.
Цей шлях не міг би відбутися без Володимира Сисенка, який побудував команду. Проте сам керманич полтавців, на жаль, не міг розділити радість від перемог своїх підопічних: протягом весняної частини сезону Володимир Анатолійович перебував на лікуванні. Хлопці ж билися не лише за свою мрію, а й за тренера, якому хотіли подарувати позитивні емоції.
До останнього туру в чемпіонській групі точилася боротьба між трьома командами, які визначали, хто зіграє в перехідних іграх, а хто потрапить напряму. Єдиним, хто вирішив достроково питання підвищення в класі, став Епіцентр. СК Полтава, Металіст 1925 та Кудрівка розігрували між собою долю путівки в УПЛ. В останньому турі першості все було в руках нашого колективу. Будь-який позитивний результат у грі з Металістом приносив полтавцям срібні нагороди і пряму путівку до УПЛ. І мрія багатьох стала реальністю: полтавці переграли харків’ян в Ужгороді завдяки переможному голу Євгена Стрельцова.
Під час літньої відпустки полтавці створили команду U-19, основу якої склали вихованці кременчуцького Кременя. Окрім цього, клуб має власну ДЮСШ, яку почали будувати 2022 року з наймолодших вікових груп. Нині в ДЮСШ СК Полтава налічується п’ять вікових груп 2014 -2019 р.н. Полтавці - постійні учасники місцевих змагань. З 2024 року юні містяни дебютували у чемпіонаті Полтавської області ДЮФЛ.
Свій дебютний сезон СК Полтава вимушений проводити не вдома. Домашньою ареною для містян став стадіон Зірка у Кропивницькому. Проте полтавці працюють над створенням власної арени. За проєктом новий стадіон містян буде побудований на 10 000 індивідуальних місць. Також комплекс включатиме тренувальні поля, манеж та базу.