Tulitanssi on syntynyt Mwanzassa, Tanzaniassa, Victoria-järven rannalla. Sisi Majitun taiteellinen johtaja Ally Milao oppi tulitanssin Bagamoyo, jossa tulitanssi on muokkautunut nykyiseen muotoonsa. Tulitanssista kerrotaan seuraavaa tarinaa:
“Eräänä päivänä Sukuma-heimon rummuttajat lähtivät kylästään juhliin. 9-vuotias Maria-niminen tyttö kuuli rumpujen äänen, kun rummuttajat kävelivät hänen kotinsa ohi. Hän lähti kotoaan liittyäkseen heihin, tanssien ja laulaen mukana toisten kanssa. Liikeen ja ääneen lumoissa hän kulki huomaamattaan kauas kotoa kunnes eksyi eikä enää löytänyt tietään takaisin kotiinsa. Oli jo tullut pimeä ja Marian perhe oli huolissaan, kun tyttöä ei löytynyt mistään. He ilmoittivat kylän pormestarille, että Maria on kadonnut ja tämä keräsi heti joukon kyläläisiä, jotka lähtivät Mariaa etsimään. Etsiessään tyttöä he lauloivat samalla laulua, jotta tyttö kuulisi heidät: “Iyayaya Mari alihe iyayaya”, missä Maria on? Muutaman tunnin etsintöjen jälkeen Maria löytyi ja hänet tuotiin takaisin perheensä luo. Vaikka oli jo keskiyö, koko kylä riemuitsi tytön löytymisestä niin, että sen kunniaksi järjestettiin isot juhlat, jotka kestivät läpi yön. Monet tulitanssin liikkeistä on poimittu sooloesityksistä, joita sen yön juhlissa nähtiin kyläläisten tanssiessaan soihtujensa kanssa.”
Sisi Majitu 