Menurut catatan sejarah, gandrung pertama kalinya ditarikan oleh para lelaki yang didandani seperti perempuan dan, menurut laporan Scholte (1927), instrumen utama yang mengiringi tarian gandrung lanang ini adalah kendang. Pada saat itu, biola telah digunakan. Namun demikian, gandrung laki-laki ini lambat laun lenyap dari Banyuwangi sekitar tahun 1890an, yang diduga karena ajaran Islam melarang segala bentuk transvestisme atau berdandan seperti perempuan. Namun, tari gandrung laki-laki baru benar-benar lenyap pada tahun 1914, setelah kematian penari terakhirnya, yakni Marsan.
Menurut sejumlah sumber, kelahiran Gandrung ditujukan untuk menghibur para pembabat hutan, mengiringi upacara minta selamat, berkaitan dengan pembabatan hutan yang angker.
Gandrung wanita pertama yang dikenal dalam sejarah adalah gandrung Semi, seorang anak kecil yang waktu itu masih berusia sepuluh tahun pada tahun 1895. Menurut cerita yang dipercaya, waktu itu Semi menderita penyakit yang cukup parah. Segala cara sudah dilakukan hingga ke dukun, namun Semi tak juga kunjung sembuh. Sehingga ibu Semi (Mak Midhah) bernazar seperti “Kadhung sira waras, sun dhadekaken Seblang, kadhung sing yo sing” (Bila kamu sembuh, saya jadikan kamu Seblang, kalau tidak ya tidak jadi). Ternyata, akhirnya Semi sembuh dan dijadikan seblang sekaligus memulai babak baru dengan ditarikannya gandrung oleh wanita.
Tradisi gandrung yang dilakukan Semi ini kemudian diikuti oleh adik-adik perempuannya dengan menggunakan nama depan Gandrung sebagai nama panggungnya. Kesenian ini kemudian terus berkembang di seantero Banyuwangi dan menjadi ikon khas setempat. Pada mulanya gandrung hanya boleh ditarikan oleh para keturunan penari gandrung sebelumnya, namun sejak tahun 1970-an mulai banyak gadis-gadis muda yang bukan keturunan gandrung yang mempelajari tarian ini dan menjadikannya sebagai sumber mata pencaharian di samping mempertahankan eksistensinya yang makin terdesak sejak akhir abad ke-20.
Tata busana penari Gandrung Banyuwangi khas, dan berbeda dengan tarian bagian Jawa lain. Ada pengaruh Bali kerajaan Blambangan yang tampak.
Busana untuk tubuh terdiri dari baju yang terbuat dari beludru berwarna hitam, dihias dengan ornamen kuning emas, serta manik-manik yang mengkilat dan berbentuk leher botol yang melilit leher hingga dada, sedang bagian pundak dan separuh punggung dibiarkan terbuka. Di bagian leher tersebut dipasang ilat-ilatan yang menutup tengah dada dan sebagai penghias bagian atas. Pada bagian lengan dihias masing-masing dengan satu buah kelat bahu dan bagian pinggang dihias dengan ikat pinggang dan sembong serta diberi hiasan kain berwarna-warni sebagai pemanisnya. Selendang selalu dikenakan di bahu.
Kepala dipasangi hiasan serupa mahkota yang disebut omprok yang terbuat dari kulit kerbau yang disamak dan diberi ornamen berwarna emas dan merah serta diberi ornamen tokoh Antasena, putra Bima yang berkepala manusia raksasa namun berbadan ular serta menutupi seluruh rambut penari gandrung. Pada masa lampau ornamen Antasena ini tidak melekat pada mahkota melainkan setengah terlepas seperti sayap burung. Sejak setelah tahun 1960-an, ornamen ekor Antasena ini kemudian dilekatkan pada omprok hingga menjadi yang sekarang ini.
Busana untuk tubuh terdiri dari baju yang terbuat dari beludru berwarna hitam, dihias dengan ornamen kuning emas, serta manik-manik yang mengkilat dan berbentuk leher botol yang melilit leher hingga dada, sedang bagian pundak dan separuh punggung dibiarkan terbuka. Di bagian leher tersebut dipasang ilat-ilatan yang menutup tengah dada dan sebagai penghias bagian atas. Pada bagian lengan dihias masing-masing dengan satu buah kelat bahu dan bagian pinggang dihias dengan ikat pinggang dan sembong serta diberi hiasan kain berwarna-warni sebagai pemanisnya. Selendang selalu dikenakan di bahu.
Kepala dipasangi hiasan serupa mahkota yang disebut omprok yang terbuat dari kulit kerbau yang disamak dan diberi ornamen berwarna emas dan merah serta diberi ornamen tokoh Antasena, putra Bima yang berkepala manusia raksasa namun berbadan ular serta menutupi seluruh rambut penari gandrung. Pada masa lampau ornamen Antasena ini tidak melekat pada mahkota melainkan setengah terlepas seperti sayap burung. Sejak setelah tahun 1960-an, ornamen ekor Antasena ini kemudian dilekatkan pada omprok hingga menjadi yang sekarang ini.
Selanjutnya pada mahkota tersebut diberi ornamen berwarna perak yang berfungsi membuat wajah sang penari seolah bulat telur, serta ada tambahan ornamen bunga yang disebut cundhuk mentul di atasnya. Sering kali, bagian omprok ini dipasang hio yang pada gilirannya memberi kesan magis.
Penari gandrung menggunakan kain batik dengan corak bermacam-macam. Namun corak batik yang paling banyak dipakai serta menjadi ciri khusus adalah batik dengan corak gajah oling, corak tumbuh-tumbuhan dengan belalai gajah pada dasar kain putih yang menjadi ciri khas Banyuwangi. Sebelum tahun 1930-an, penari gandrung tidak memakai kaus kaki, namun semenjak dekade tersebut penari gandrung selalu memakai kaus kaki putih dalam setiap pertunjukannya.
Musik pengiring untuk gandrung Banyuwangi terdiri dari satu buah kempul atau gong, satu buah kluncing (triangle), satu atau dua buah biola, dua buah kendhang, dan sepasang kethuk. Di samping itu, pertunjukan tidak lengkap jika tidak diiringi panjakpengudang (pemberi semangat) yang bertugas memberi semangat dan memberi efek kocak dalam setiap pertunjukan gandrung. Peran panjak atau kadang-kadang disebut dapat diambil oleh pemain kluncing.