His father, Burlaki Barlas converted to Islam, so he was born to a Muslim family and as an adult, assumed the title Hajji, having participated in the hajj pilgrimage to Mecca.
Hajji Beg is first mentioned in 1358 or 1359, when he participated in the overthrow of the Qara'unas ‘Abdullah, who was effectively in control of the southern Chagatai Khanate.
'Abd Allah, who had recently taken power, was young and inexperienced, and his move to Samarkand threatened Hajji Beg, whose territories were centered in the nearby city of Kish.
Together with another tribal leader named Buyan Suldus, Hajji Beg removed him from power and killed his puppet khan Shah Temur.
Buyan Suldus' refusal to enforce his authority, as well as a continuing state of chaos within the Chagatai ulus, led to the Khan of Moghulistan, Tughlugh Timur, to invade in 1360.
The two sides met in battle, and while its outcome is disagreed upon, it caused the Barlas emirs as well as the army to defect back to Hajji Beg.