Село Лелюхівка знаходиться на берегах річки Полузір'я, вище за течією на відстані 0,5 км розташоване село Назаренки, нижче за течією примикає смт Нові Санжари. Через село проходить автомобільна дорога М22 (E584).
За даними на 1859 рік у власницькому та козацькому селі Кобеляцького повітуПолтавської губернії, мешкало 1300 осіб (634 чоловічої статі та 666 — жіночої), налічувалось 98 дворових господарств, існувала православна церква[2].
У Лелюхівці знаходиться автобусна зупинка, прикрашена мозаїками радянського періоду. Фотограф Крістофер Хервіг (Christopher Herwig) включив світлину з зображенням лелюхівської автобусної зупинки до фотоальбому «Радянські автобусні зупинки» (Soviet Bus Stops), у якому зібрані фотографії артистичних автобусних зупинок у пост-радянських держав[4].
12 червня 2020 року, відповідно до розпорядження Кабінету Міністрів України № 721-р «Про визначення адміністративних центрів та затвердження територій територіальних громад Полтавської області», село увійшло до складу Новосанжарської селищної громади[5].
19 липня 2020 року, в результаті адміністративно - територіальної реформи та ліквідації Новосанжарського району, село увійшло до складу новоутвореного Полтавського району Полтавської області[6].
Археологія
Скарб із села Лелюхівки Полтавської області, який випадково знайшов Володимир Корсун під час проведення робіт по укріпленню берегів річки Ворони у 2000 році.
Він містить понад 13 300 предметів – монет та інших речей. Переважно це європейські монети кінця 16 – початку 18 століття, зокрема, золоті дукати і срібні талери. В ньому також є 40 ужиткових речей: 39 ґудзиків трьох різних типів із високоякісного срібла і один перстень-сигнет (печатка).
Велика кількість монет та великий часовий проміжок їх карбування дозволяє ґрунтовно відобразити грошовий обіг на українських теренах, зокрема в Гетьманщині, у перші десятиліття 18 століття. Відомо, що в Гетьманщині в той час продовжували користуватися європейськими грошима. Частина монет промаркована клеймами московського царя – зображенням вершника зі списом та роком маркування.
Історія скарбу достеменно невідома. Можливо, це була військова скарбниця.
Існує версія, що скарб пов’язаний із гетьманом «Ханської» України Петром (Петриком) Іваненком. Він походив із Полтавщини.