Свій початок Лелюхівський заклад освіти бере ще з кінця XIX століття, початку XX ст. У Кліровій книзі Полтавської єпархії на 1902 рік зроблено такий запис про Лелюхівську церкву:
«397, Села Лелюховки Георгіївська церков, деревяная, на каменном фундаменте, в одной святи с такой же колокольнею, холодная, построенная в 1771 году запорожскими козаками Иоанном Непий-Брагой и Заковом Пархоменко; Церковная библиотека; церковно – приходская школа – помещается в собственном доме; дом для квартиры священника; земля при церкви усадьбенной - в ширину 7, в длину 3саж. погост прежней церкви в длину 20, в ширину 23 саж. погост настоящей церкви 1070 кв. саж., усадьбенной 1130 кв. саж., пахатной 30 дес. 442 кв. саж., ружной 33 дес.; жалованья в год священнику 140 руб., псаломщику 36 руб., церковь от консистории в 34 верстах.
Прихожан 1155 о.м.п. и 1149 о.ж.п.
В приходе хутора Малый – Кобелячек.
Священник Иоанн Матвеев Головков – в сане
Псаломщики: диакон - Віктор Петров Ващинський – в сане 1894г. и Евфимий Петров Браславский – в должности
Церковный староста козак Іаков Архипов Варрава»
Спочатку це була двокласна церковно-приходська школа. Завідував школою в 1904 році священик Іоан Головков, учителями були його дружина Наталія Головкова та Гавриїл Логвиненко. Про це свідчить похвальний лист Царенко Домнікії, датований 11 травням 1904 року. Дівчата навчалися окремо від хлопців. Основними предметами були Закон Божий, слов’янська мова, арифметика, а книги псалтир – євангеліє.
В після революційний час церква була закрита, а потім зруйнована. Приміщення школи в 1929 – 1930 роках знаходилося біля нинішньої траси Полтава – Кременчук (зі спогадів тодішнього учня першого класу Явтушенка Івана Пилиповича). Директором був Слюсаренко, а вчителем Рогозін Лев Львович (доцент Полтавського педінституту).
Коли в Україні проводилася сталінська політика колективізації (1928-1930рр.), частину заможних селян було розкуркулено, така доля спіткала селянина Вараву. В його жилі будинки в 30-ті роки була переведена школа. Вона стала чотирикласною. Завідував нею Лашко Федір Дем’янович. Церковні книги забрали, а видали букварі. Хлопці і дівчата почали навчатися разом. Першою вчителькою стала Шраменко Марія Юхимівна. В той час навчалися такі учні: Смоловий І.Я, Смоловий М.І, Охрей О.І та інші. Коли селяни утворили в 1928 році колгосп «До кращого життя», в тому ж році в школі почав діяти перший піонерський загін.
У роки голодомору 1930 – 1933 років велика частина дітей залишилася сиротами. Тому в приміщені школи було створено патронат, у якому перебували діти, залишені напризволяще, з хуторів і сіл Новосанжарського району. Голова колгоспу «До кращого життя» Дерев’янко виділяв продукти для харчування. Їсти варили для сиріт Решетило Мотря Гаврилівна та Брижань Ганна Іванівна. А в приміщені школи знову проводились заняття. В 1934 – 1936 році директором школи був Лашко Федір Дем’янович, а вчителями працювали Канюка Петро Якович, Кущ Іван Гаврилович, Гусак Яків Сергійович, Човган, Непорада Галина Мефодіївна, Мокляк Катерина Якимівна, Іванюк Феня Василівна.
В передвоєнні роки директором школи був Канюка Яків Петрович, а вчителькою була його дружина Непорада Галина Мефодіївна На той час піонери проводили велику антирелігійну пропаганду. Вчителька Комишова Євдокія Семенівна створила гурток юних безвірників.
Війна….
Під час фашистської окупації німці вимагали, щоб в школі висіли ікони і вивчався божий закон. Вчителька Шраменко Марія Юхимівна відмовилася і школу закрили.
Осінь 1943 року. Відгриміли бої в селі Лелюхівка. У село вступили передові частини Радянської Армії. Почав відновлювати свою роботу колгосп, головою якого був обраний Ремезов П.І. В селі відновлювала свою роботу також початкова школа. Вчителі Непорада Галина Мефодіївна та Шраменко Марія Юхимівна приймали дітей до школи. За направленням райкому комсомолу до школи піонервожатою прийшла працювати Коба О.П. – енергійна дівчина, яка на все життя пов’язала свою долю з дітьми. 1 січня 1944 року відкрилася початкова школа, завідуючою була Сербін Марія Федорівна. У цей час школа налічувала 165 учнів, 4 класи. Разом з тим ,що учні навчалися в школі, вони ще й саджали картоплю, моркву, капусту, буряки, соняшник. Все оброблялося учнівськими руками – і поління, і збирання. Ці продукти частинами здавалися в колгосп, а частинами використовували для харчування дітей. Був організований гарячий сніданок та обід для учнів.
В 1949 школу перейменовано в семирічну. Зросла кількість учнів у школі, а з нею і чисельність педагогічного колективу. Стали працювати Горошоченко Галина Тимофіївна – вчителем української мови та літератури, Вакуленко Марія Сергіївна - учитель російської мови та літератури, Гринько Юхим Кіндратович – вчитель історії та географії. Учителі початкових класів Шраменко Марія Юхимівна, Устименко Устина Леонтівна. Учителі початкових класів вели по два класи, класи – колективи.
Минали літа. Все ставало на свої місця. В 1951 році школа одержала нового директора – Огій Меланію Артемівну. Початкові класи були класи – комплекти. Із сходинки на сходинку до сонячних вершин знань вели учнів їх наставники – вчителі Фешин Б.В., Худолій В.О., Усенко У.Л., Вакуленко М.С., Ніценко Т.І., Болтушенко П. У ці роки в початкових класах почала працювати ветеран педагогічної праці Зубашич Марія Григорівна
У 1966 році піонервожатою школи стає Куць (Васильківська) Надія Павлівна. Це вона зі своїм ентузіазмом і запальним вогником у серці організувала учнів на добрі справи. В школі розгорнулася велика пошукова робота. Багато сімей дізналося, де поховані їх рідні, які воювали на фронтах другої світової.
В 1972 році директором Лелюхівської восьмирічної школи стає Варава Іван Кирилович. Його дружина Лідія Миронівна працювала учителем початкових класів. Але школа так і знаходилася в непристосованих для школи приміщеннях. Ставилися клопотання перед районним відділом освіти про будівництво нової школи. І ось у 1975 році директор школи Ірза Петро Вікторович домігся, щоб було розпочато будівництво нової школи.
За кошти колгоспу «Маяк комунізму» зводилася нова школа в центрі села.
І ось настало 1 вересня 1979 року. Саме тоді відкрила двері новозбудована школа. Яка то була радість! Ключ до знань з рук будівельників отримав директор школи Прокопенко Сергій Якович.
Поряд з директором працювали завуч школи Скирда Зоя Павлівна, вчитель української мови Сальна Валентина Якимівна, учитель німецької мови Явтушенко Людмила Олексіївна, вихователь Мокляк Антоніна Гнатівна, вчитель математики Литовченко Олена Іванівна, Васильківська Надія Павлівна. Піонервожатою тоді в школі була Вишнева Віра Гнатівна. Піонерська дружина школи носила ім’я Валентини Терешкової. Цікаво проходили дні народження піонерської організації, коли біля вогнища діти підбивали підсумки і нагороджували кращих.
Скільки літ прошуміло, а вона як навчала, так і навчає, бо це покликання школи – сіяти у дітей розумне, добре, вічне. Багато випускників випурхнуло з її стін. Серед них : лікарі, інженери, агрономи, зоотехніки, архітектори, вчителі. Школа вивчила і гордиться всіма тими, хто в серці береже настанови своїх учителів.
Естафету керівництва в 1983 році прийняла Сальна Валентина Якимівна. Педагогічний колектив складався з 18 педагогів, а учнівський з 180 учнів.
Учні школи неодноразово брали участь і займали призові місця на районних предметних олімпіадах, різноманітних конкурсах, фестивалях, змаганнях. Традиції школи, які були започатковані здавна, зберігаються і зараз.
Учителями, які внесли великий вклад у розвиток шкільної освіти в селі, нині є пенсіонери: Варава Лідія Миронівна – відмінник народної освіти, Скирда Зоя Павлівна - відмінник народної освіти, Явтушенко Людмила Олексіївна, удостоєна урядової нагороди - «Ордена Трудового Червоного Прапора»., воістину народна вчителька – Зубашич Марія Трохимівна, вчитель-методист Литовченко Олена Іванівна, біолог – Смолова Ольга Іванівна.
Їх естафету міцно тримають і продовжують: лауреат Всеукраїнського конкурсу «Учитель року – 2002» в номінації «Хімія», учитель-методист Жильченко Володимир Анатолійович, учитель-хранитель минувшини школи, «Старший учитель» - Двірна Віра Гнатівна, вихователь-методист, «Старший учитель» - Мокляк Антоніна Гнатівна, «Відмінник освіти України», біолог-еколог за покликанням – Жильченко Олеся Тихонівна, вчителі молодших класів – Свищ Людмила Миколаївна, Улянич Валентина Григорівна, Горбенко Тетяна Степанівна, Гужва Любов Іванівна, вчителі точних наук: старший учитель математики – Яременко Людмила Володимирівна, Січкар Любов Володимирівна, вмілий мовник – Марченко Олена Миколаївна.
З 2010 року директором школи став молодий, талановитий та енергійний керівник – Жильченко Володимир Анатолійович. Очоливши школу, він поставив собі за мету – продовжувати всі добрі традиції напрацьовані багатьма поколіннями вчителів школи та досягти нових успіхів і звершень в ім’я процвітання і слави Лелюхівської школи – храму Науки, Миру і Добра.
Рішенням сімнадцятої сесії Новосанжарської селищної ради восьмого скликання від 24 грудня 2021 року №33 Лелюхівська загальноосвітня школа І-ІІ ступенів перейменована на Лелюхівську гімназію Новосанжарської селищної ради Полтавської області.