He served as the governor of Iraq during the reigns of Abd al-Malik and al-Walid I of the Umayyad empire. Hajjaj began his career in 691 when he lead troops against the then governor of Iraq, who was outside the Umayyad sphere of influence. After defeating that governor, he was sent to the Hejaz where he laid seige to Mecca and captured the city, killing Ibn Al-Zubayr and putting all of the Muslim empire back under the banner of the Umayyads.
While governing the Hejaz, Hajjaj was known for his severe form of rule, and he was then sent to be the governor of Iraq. Even here, his reputation continued and was not helped by his crushing of a Kharijite rebellion. For these sucesses, Hajjaj was also made governor of some provinces in Persia where he was again tasked with putting down rebellions. However his tactics also led him to make many enemies, who would come to power after his death.
With the ascent of al-Walid I, Hajjaj's reputation grew due to his selection and deployment of numerous sucessful generals who expanded the Islamic empire. Hajjaj was given these powers due to his high status in the Umayyad government, and he exhibited a lot of control over the provinces that he goverened. Among these generals was the teen-aged Muhammad bin Qasim, who was sent to Sindh in India. Other generals were sent to Transoxiana.
The sucesses of his generals gave Hajjaj great prestige, which was furthered by his introduction of vowel marks in written Qurans, something that would go on to be implimented in the Arabic language. Hajjaj would die in 714.
The year after Hajjaj died, al-Walid would die as well, and his brother, Suleiman would come to power. Suleiman was indebted to many opponents of Hajjaj for their political support in getting him elected caliph. Thus, he recalled all generals sent by Hajjaj, and had them tortured to death in prison, ignoring their great victories.
The relationship between Hajjaj bin Yousef and Muhammad bin Qasim has always been one of great debate. Many classical accounts list Hajjaj as being his uncle, or father in law. But this is debatable, and it seems more likely that they were distant cousins.