Liaudies etimologija byloja, kad miestelio pavadinimas kilęs nuo žodžio „liūnas“ – esą tame liūne nuskendusi prancūziškai kalbėjusi dvaro ponia (prancūzų kalboje prieš vyriškosios giminės daiktavardžius pridedamas artikelis le, t. y. gavosi le liūnas).
Nuo XVII a. pradžioje minimas Leliūnų dvaras ir kaimas. Pirmoji Leliūnų bažnyčia pastatyta 1698 m. Miestelis pradėjo augti, kai pro Leliūnus buvo nutiestas plentas Kaunas–Zarasai. 1853 m. minima parapinė mokykla, o 1788 m. buvo pastatyta antroji – Šv. Juozapo parapijinė bažnyčia.[3]1863 m. miestelio apylinkėse kovėsi K. Lukošiūno sukilėlių būrys. XIX a. Leliūnai buvo miestelis ir dvaras Vilkmergės apskrities Alantos valsčiuje.[4][5] Vietos gyventojai prisidėjo prie lietuviškų knygų platinimo spaudos draudimo laikais, dalyvavo 1905 m. revoliucijos įvykiuose.
XX a. tarpukariu miestelyje veikė urėdija. 1941 m. apie 50 Leliūnų žydų nužudyta prie Utenos. 1941–1944 m. naciai miestelio mokykloje įsteigė karo belaisvių stovyklą. Pirmaisiais sovietinės okupacijos metais leliūniškiai rėmė Lietuvos partizanus ir patys aktyviai dalyvavo pasipriešinimo kovose.1949 m. lapkričio mėn. Leliūnų valsčiuje buvo įrengtas Vytauto apygardos Liūto partizanų rinktinės partizanų štabo bunkeris, 1950 m. aptiktas saugumo darbuotojų. Sovietmečiu buvo kolūkio centrinė gyvenvietė.[6]1945 m. įkurta biblioteka, kultūros namai, senelių globos namai, medicinos punktas.
XX a. 8-ajame dešimtmetyje prijungtas Leliūnų kaimas, vėliau vėl atskirtas nuo miestelio. 1998 m. ant parapijos namų sienos atidengta lenta nužudytų partizanų atminimui. 2004 m. patvirtintas Leliūnų herbas.