Folklorní soubor Leluja vznikl na podzim roku 2008 v obci Provodov. U jeho založení stály Hana Tesařová a Eva Janíková. Jejich snahou bylo seznámit děti i veřejnost s tradičním způsobem života na luhačovickém Zálesí a připomenout jim lidové zvyky a obřady, které zde byly v minulosti provozovány, avšak postupem času vymizely. Vedoucí souboru se stala Eva Janíková a tvořilo jej okolo třiceti dětí z obce Provodov. Zřizovatelem byla ZUŠ Morava.
Zpočátku se vystoupení souboru konala jen v rámci obce. Došlo k obnově některých lidových zvyklostí a postupně se rekonstruoval také záleský kroj. Během následujících let se Leluja rozrostla o tanečníky z dalších vesnic, začala se objevovat při různých příležitostech v okolí a dnes vystupuje na folklorních festivalech doma i v zahraničí.
V roce 2011 rozšířila své působení také na Řetechov. V listopadu se soubor osamostatnil a přešel pod nově vzniklé občanské sdružení Leluja, o. s. Ve stejné době k němu přibyla hudecká muzika (ve složení troje housle, klarinet a basa), která děti a tanečníky doprovázela při vystoupeních. Ta byla v lednu 2012 doplněna na cimbálovou (ve složení troje housle, viola, cimbál a basa). V červnu 2012 uspořádala Leluja folklorní festival Hore Provodovem, kterého se zúčastnily další tři moravské dětské soubory. Během srpna se k ní pak připojilo několik dospělých tanečníků a postupně začala vznikat chasa.
V roce 2013 oslavil soubor pět let své existence. V tomto roce navíc při souboru vznikla další složka, ženský sbor, a na podzim Leluja nahrála upomínkové album záleských písní s názvem První plody.
V dalších pěti letech svého působení dosáhl soubor větší známosti mezi ostatními folklorními soubory nejen na Moravě. Pozvání na festivaly příbývalo a vedení souboru bylo nuceno rozšířit členskou základnu o další složky a kurzy. K obvyklým souborovým tanečním skupinám přibyly folklorní taneční pro veřejnost a mužský sbor.
Úroveň souboru stále stoupala, což dokazují úspěchy na krajských kolech tanečních přehlídek a regionálních kolech pěveckých soutěží. Stále přibývalo i zvyků, které soubor obnovil nejen na Provodově. Festival Hore Provodovem se rozrostl na festival třídenní s mezinárodní účastí.
Zřizovatel Leluja, o.s. v roce 2015 změnil svoji právní formu na zapsaný spolek. Od té chvíle je zřizovatelem Leluja, z.s.
V roce 2016 vzestup souboru musel trochu přibrzdit a to kvůli absenci umělecké vedoucí z důvodu mateřství. Díky tomu se mezi členy objevily nové šikovné vedoucí, které vedou své dětské skupinky doposud.
V roce 2017 opustila soubor cimbálová muzika, která si dala název „Cyril“ a soubor obratem vytvořil novou muziku, složenou ze svých dětských členů. Muzička měla své první vystoupení 1. 7. 2017 v Bystřici pod Hostýnem na „MFF Na Rynku v Bystřici“ ve složení šestery housle, flétna a harmonika.
V roce 2018, tedy 10 let od vzniku, fungovaly v souboru tyto složky: Malá Leluja Provodov, Malá Leluja Řetechov, Velká Leluja, Ženský sbor, Muzička a další příležitostná skupina tanečně-pěvecká.
Po překonání krize v roce 2020 se soubor opět pustil do práce, doplnil taneční složku o nové tanečníky a tanečnice. V roce 2022 byla opět otevřena skupina Malúšat – dětí od 2,5 let. Tyto děti si spolu s rodiči nebo sourozenci v souboru hrály a učily se prvním krůčkům. V současné době soubor působí pouze na Provodově. Je zván na mezinárodní festivaly v ČR i v zahraničí, profilové programy NÚLK a dalších muzeí, pořádá každoročně folklorní plesy (od roku 2013) a nadále si drží festival Hore Provodovem jako bienále v sudé roky (kromě vynechaného roku 2020), je spolupořadatelem MFF Písní a tancem Luhačovice a čítá každoročně kolem 60 členů.
Muzika je ve složení Harmonika, troje housle, basa.
Kromě Malé Leluje a Velké Leluje se opět rozrostly řady ženského sboru, který vystupoval i na MFF Strážnice stejně jako taneční složka.
Významné festivaly, kterých se soubor Leluja zúčastnil:
Slavnosti vína a otevřených památek Uherské Hradiště (2010–2019, 2022-2024)
Otevírání pramenů Luhačovice (2011–2024)
MFDFS Písní a tancem Luhačovice (2011, 2014, 2016–2024)
FF Mikulášský jarmark Buchlovice (2011)
FF Hore Provodovem Provodov (2012, 2014, 2016, 2018, 2022, 2024)
MFF Májíček Zlín (2012, 2023)
MFF Pod hradem Malenovice (2012)
Vystoupení v Lednických Rovních Slovensko (2012)
MFF Pod skalkou Slovensko – Liptovský Mikuláš (2012)
FF Metlářský jarmark Zubří (2013)
MFF Dožínky Zlínského kraje (2013, 2016, 2017, 2018, 2021-2023)
Vystoupení v Piešťanech Slovensko (2013)
Soutěžní přehlídky s postupem do regionálního/krajského kola do Rožnova pod Radhoštěm (2013, 2017)
Setkání souborů luhačovského Zálesí (2013, 2014)
FF Dětské krojované hody Poddvorov (2014)
MFF Liptálské slavnosti Liptál (2014)
Mezinárodní program Folklór bez hraníc Sobrance Slovensko (2014)
Profilový program Velikonoce ve skanzenu v Rožnově pod Radhoštěm (2014, 2023)
MFF Kunovské léto Kunovice (2017)
MFF Na rynku v Bystřici Bystřice pod Hostýnem (2017)
MFF Léto na Soláni Velké Karlovice (2017)
Vystoupení v senátu PČR v Praze (2017)
Profilový program Dožínky ve skanzenu ve Strážnici (2018)
MFF Brno (2018)
Růže pro Lidice (2019)
Krojová pouť na Zelenou Horu u Žďáru nad Sázavou (2019)
MFF Strážnice – v hlavním programu věnovaném Zdence Jelínkové (2022), v programu Rozkvetlé zpívání (2023)
MFF Krojové bábiky Kežmarok, Poprad – Slovensko (2023)
Moravské chodníčky Napajedla (2023)
Adámkovy folklorní slavnosti Hlinsko – Betlém (2023)
A další vystoupení v okolních obcích (Ludkovice, Doubravy, Kelníky, Pozlovice, Březůvky, Řetechov atd.)
Vynášení Mařeny, Provodov, březen 2009
První vynášení Mařeny, tehdy ještě bez krojů
Vynášení Mařeny, Řetechov, březen 2012
Vystoupení chasy, Doubravy, červen 2013
Setkání souborů Luhačovského Zálesí
Růže pro Lidice, Lidice, červen 2019
Rekonstrukce tance z Pozlovic, MFF Strážnice, červen 2022