The founding date of the Bukhar Khudahs remains unknown; the 10th-century Iranian historian Narshakhi is known to have mentioned several names of rulers of Bukhara, but it is not known if they were all from the same dynasty.

The first ruler mentioned with the title of Bukhar Khudah is named Bidun, who was killed in 681 by the Umayyad general Salm ibn Ziyad during the first Arab attempts to conquer Transoxiana.

However, the kingdom was in reality controlled by Tughshada's mother, who is only known by her title of Khatun of Bukhara,[1] and is celebrated in the local historical tradition for her wisdom and capable management.

[2] She is reported to have held court daily, "inquired into the affairs of state and issued orders and prohibitions," while at a distance stood "two hundred youths from the landowners and the princes ready for service, girded with gold belts and bearing swords.

The brutality of the sack of Paykand shocked the Sogdian world, and led the nobles of Bukhara under Khunuk to make an alliance with the Wardan Khudah.

Later, in 712/3, in order to spread Islam in Bukhara, Qutayba built a mosque in the city's citadel, and even encouraged the natives to convert by paying them to attend the prayers.

[11] The Abbasid general Abu Muslim Khorasani sent an army under Ziyad ibn Salih to suppress the rebellion, but the rebels managed to emerge victorious.