SEJARAH mencatat, tayub muncul pada zaman Kerajaan Kediri, abad ke-11 Masehi. Mulai berkembang di Jawa bagian timur dan tengah, tradisi ini tercatat dalam buku Kakawin Bharata Yudha karya Mpu Sedhah dan Mpu Panuluh pada 1079 Saka atau 1157 Masehi. Pada pupuh XIII bait ke-8 terdapat kisah para Pandawa yang sedang nayub. Prof Dr. R.M. Sutjipta Wirjosuparto (1968) menerjemahkan nayub sebagai "menari-nari dan bergembira dengan riuhnya"