Being in need to form an alliance with an ally who could help him against the threat of the Mamluks who had fled to Syria,Aybak decided in 1257 to marry the daughter of Badr ad-Din Lu'lu', the emir of Mosul. Shajar al-Durr, who already had disputes with Aybak felt betrayed by the man who she made sultan, and had him murdered after he had ruled Egypt seven years. Shajar al-Durr claimed that Aybak died suddenly during the night but his Mamluks (Mu'iziyya), led by Qutuz, did not believe her and the servants involved confessed under torture.

On 28 April, Shajar al-Durr was stripped and beaten to death with clogs by the bondmaids of al-Mansur Ali and his mother. Her naked body was found lying outside the Citadel. Aybak's 11-year-old son Ali was installed by his loyal Mamluks (Mu'iziyya Mamluks), led by Qutuz. Qutuz becomes the vice-sultan.