Little is known about his life before the age of 20, when he and childhood friend Nawaf al-Hazmi went to Bosnia and Herzegovina to fight with the mujahideen in the Bosnian War.
Hänen nuoruudesta ei tiedetä juurikaan, mutta 20-vuotiaana Mihdhar ja hänen lapsuudenystävä Nawaf al-Hazmi matkustivat Bosniaan taistellakseen mujahideenien rinnalla Bosnian sodassa.