Турецкие вторжения первой половины XVI века превратили эту область в пограничную территорию: земли к западу от будущего комитата Хайду вошли в состав Османской империи, земли к северу признали власть Габсбургов, а Дебрецен был включён в состав полунезависимого Трансильванского княжества. Борьба между этими тремя государствами за власть в венгерских степях не прекращалась, территория Хайду периодически опустошалась турецкими, австрийскими и трансильванскими войсками.
В конце XVI века в регионе усилилась власть австрийских Габсбургов, которые пытались подчинить Трансильванию. Однако против австрийцев развернулось народное движение гайдуков, выходцев из венгерских, славянских и румынских крестьян, взявших в руки оружие для защиты своих домов. Во главе гайдуков встал Иштван Бочкаи, который в 1604 г. разгромил австрийские войска в битве при Альмошде и взял Дебрецен. В 1605 г. Иштван Бочкаи стал князем Трансильвании, а в следующем году добился от Габсбургов признания независимости княжества и передачи ему приграничных земель. За помощь, оказанную в борьбе с Габсбургами, Иштван Бочкаи в 1605 г. даровал гайдукам территорию между Дебреценом и Тисой с правами самоуправления. Так возник Хайдушаг, особый административный регион, не включённый в комитатскую систему и пользующийся определёнными привилегиями. В 1614 г. гайдуки получили дворянский статус. Гайдуцкие конные войска, набираемые в Хайдушаге в дальнейшем играли важные роли во всех национальных восстаниях в Венгрии против иностранной власти (включая войны Габора Бетлена и восстание Ференца Ракоци II).
В 1690 г. с изгнанием турок и ликвидацией независимого Трансильванского княжества, Хайдушаг был включён в состав Венгерского королевства Габсбургов. Определённые привилегии жители Хайдушага ещё некоторое время сохраняли, однако их значение с усилением централизации и унификации постепенно падало. Тем не менее, наряду с Куншагом и Ясшагом, Хайдушаг оставался одним из трёх автономных регионов Венгрии