Terdapat beberapa versi legenda Ulek Mayang. Menurut salah satu darinya, tarian ini berasal dari upacara rawatan kuno yang dilakukan oleh seorang bomoh ke atas seorang nelayan yang berada dalam keadaan tidak sedar, dipercayai telah dipukau oleh seorang putri laut yang jatuh cinta padanya. Percobaan bomoh untuk membawa balik roh nelayan itu menyebabkan putri itu menyeru lima lagi saudaranya untuk melawan bomoh tersebut. Pertarungan di antara si bomoh dan keenam-enam putri berlanjutan sehingga kemunculan putri yang ketujuh dan paling sulung.
"Ku tahu asal-usulmu”, kata putri sulung dan beliau memerintahkan semua orang, "Yang laut balik ke laut, yang darat balik ke darat".
Bomoh yang terhutang budi dan rakan-rakan nelayan menyampaikan sembahan nasi berwarna kepada sang putri, satu upacara yang kekal diamalkan sehingga kedatangan Islam, untuk menunjukkan rasa terhutang budi kepada semangat-semangat laut.
Nota: Mayang adalah bunga pohon kelapa digunakan untuk mengusir makhluk halus.