Asal usul Tarian Balai atau Ulai tidak jelas. Bagaimanapun, ia dipercayai telah bertapak di Terengganu kira-kira 300 tahun yang lalu. Kewujudan tarian ini di Kampung Bukit Gemuruh, Hulu Terengganu berkisar sekitar cerita sepasang petani iaitu Tok Jambul dan isterinya Tok Senik serta anak mereka. Apabila Tok Senik mendodoi anaknya kedengaran ada suara ghaib seolah-olah membalas pantunnya. Suara itu tetap membalas pantun Tok Senik apabila ia menyambung kerja di sawah sambil berpantun.

Suatu hari Tok Jambul bermimpi bertemu seorang lelaki yang memberitahu ada jin hendak bersuka-sukaan dengan isterinya. Lelaki itu menyuruh Tok Jambul mencacakkan beberapa batang pokok pulai serta merenjis tepung tawar di sekitar pokok tersebut menggunakan daun pisang, serta menjampinya. Akhirnya padinya subur serta menjadi dan suara ghaib itupun tiada lagi.

Pada asalnya tarian ini bersangkut paut dengan pemujaan semangat padi dan ditarikan oleh anak-anak gadis Kampung Bukit Gemuruh. Tarian ini diiringi dengan nyanyian dan menggambarkan kegembiraan petani setelah mendapat hasil.

Pergerakan tarian menggambarkan petani sedang melakukan pekerjaan sawah. Payung yang berwarna-warni sebagai simbol semangat padi diletakkan di tengah-tengah pentas dan penari menari mengelilingi payung-payung tersebut.  Peralatan menanam padi seperti cangkul, penuai padi, dan topi petani dijadikan prop persembahan.