Про час заснування та походження назви села Шостаки відомостей не збереглося. Очевидно село заснував чоловік на прізвисько (або прізвище) Шостак. Ім'я Шостак в Україні в XVI ст. давали шостій дитині за черговістю народження. Батькове ім'я могло перейти до сина вже як прізвище. Таке прізвисько могли дати й козаки комусь із своєї ватаги з різних причин. Згідно з іншим варіантом назва села Шостаки може мати походження від українізованої польської назви шостак (szostak) польської, литовської і пруської срібної монети XVI—XVII ст. вартістю в 6 грошів, карбованої з 1528 р., особливо за Сіґізмунда III 1623—1627 рр.
Під час Рум'янцевського опису населення на Полтавщині (1767—1769 рр.) село вже існувало. Тоді у Шостаках налічувалось 14 дворів та дворогосподарів. Корінний житель села Шостаки Підварчан А. С. (1937 р. н.) розповів інформацію, яка передавалась від старших людей, про те що за козацьких часів у селі стояли обозні козаки.
У 1776 році у Шостаках була Параскавіївська церква, у якій службу проводив один священик. У 1787 році в селі мешкало 145 чоловіків і 142 жінки.
У 1799—1801 роках у Шостаках було 163 жителі чоловічої статі, які сплачували податок, село належало до Полтавського повіту.
У 1899 році в джерелах знову згадується про діючу в селі дерев'яну Парасковіївську церкву. Підварчана А. С. розповів, що за переказами старожилів, біля церкви було давнє кладовище, яке не збереглось. Сама церква знаходилась біля залізниці, з південного боку (тепер на місці церкви приватні городи), за квартал на схід від діючого сьогодні також старого кладовища, якому біля 150 років.
У XIX ст. через Шостаки проклали залізничну лінія Полтава — Київ, яка почала діяти 1901 році і різділила село на дві частини північну і південну.
З розповідей старожилів, в північно-східній частині села на пагорбі шостківської балки була садиба пана Трипольського. Поміщик не мав дітей, а після подій української національної революції його родина зникла і їх подальша доля невідома.
Залишки господарських будівель садиби пана Трипольського стояли і використовувались ще в 60-тих роках минулого століття. У нижній частині шостківської балки був панський ставок де водилась риба та купалось і відпочивало сільське населення. Навколо водойми росли великі верби, гарна була місцевість, красива. Але відтоді як зник пан Трипольський не було іншого господаря, і з часом ставок замулився, заріс осокою і зник.
Після розпаду Російської царської імперії в 1917 році і поразки Української національної революції, в кінці листопада 1919 року в Полтаві та навколишніх селах надовго закріпились Радянська влада російських комуністів.
У 20-тих роках минулого століття в Шостаках була проведена колективізація і створено колгосп. Пізніше Шостаківський колгосп об'єднали з Супрунівським колгоспом «Перемога» і перетворили на бригаду. Колгоспний двір і господарство розміщувалось у колишніх господарських приміщеннях садиби пана Трипольського (клуні, сарай, вхідний погріб).
Штучний голодомор 1932—1933 років, створений російським комуністичним режимом, забрав життя багатьох односельчан.
Під час Другої світової війни з 1941 по 1943 рік в селі були розквартировані німецькі солдати очевидно з комендатури, яка знаходилась в сусідній Супрунівці. У роки окупації німецька влада насильно вивозила з села молодь на каторжні роботи до Німеччини. Деякі з них назад не повернулись, пропали безвісти.
У 1943 році, відступаючи, німецькі війська спалили село. Житель села Підварчан А. С. (на той час мав 6 років) розповів, що 22 вересня 1943 року, зранку, німецькі солдати почали палити сусіднє село Гожули, а близько обідньої пори вже запалали й Шостаки. Ще зранку, жителі північної частини села повиносили з хат і поховали найцінніші речі, а самі зібрались біля кладовища, з південного боку залізниці, і звідти бачили як декілька озброєних карателів (3, можливо 4) об'їздили село автомобілем та факелами палили їхні, вкриті соломою, оселі.
Під час війни на фронтах загинуло сорок жителів Шостаків чоловічої статі, які воювали на боці Червоній армії.
Після війни село поступово відбудувалось.
За даними перепису 2001 року населення села становило 347 осіб. Адміністративно село підпорядковане Супрунівській сільській раді. У ХІХ ст. у центральній частині села Шостаки (поблизу будинку залізничників) стояла церква (приділ Супрунівської церкви).
12 червня 2020 року, відповідно до розпорядження Кабінету Міністрів України № 721-р «Про визначення адміністративних центрів та затвердження територій територіальних громад Полтавської області», село увійшло до складу Полтавської міської громади[1].
