Killa Saifullah, still a tribal agency in administrative terms, has been a part of Zhob and all the historical descriptions available are in the context of the Zhob area. The prime historical importance of Zhob is having been a cradle of the Afghan race. In the 7th century, Hiuen Tsiang, a Chinese pilgrim has described the Afghans as living in Zhob. Early in the 13th century the country came within the sphere of the raids organised by Gengis Khan, the Mongol. In 1398 AD, an expedition against the Afghans of the area was led by Pir Muhammad, grandson of Amir Timur. Although no authentic information exist about any foreign occupation, many forts, mounds and karezes are attributed to the Mughals. Both Nadir Shah (1736-47 AD) and Ahmed Shah (1747-73 AD) extended their power through Balochistan and thenceforth Zhob remained under the more or less nominal suzerainty of the Durranis and Barakzais until it came under British protection. In the middle of the 18th century Ahmed Shah granted a sanad (certificate) to Bekar Nika, fourth in descent from Jogi and the head of the Jogizai family, conferring upon him the title and position of “Badshah or Ruler of Zhob”. This family continued to exercise authority over the Kakars until the British were first brought into contact with them.
After outbreak of the Afghan war in 1878, Zhob became a focus of the British attention when the Kakars of Zhob under the command of various sardars – the most important being Shah Jahan, Shahbaz Khan, Dost Muhammad and Bangul Khan – resisted the British authority and tried to destroy the communications. In October 1884, an expedition was sent into Zhob area to seek submission from the local dissidents. After various encounters with the Kakars of Zhob the British occupied the territory and Zhob was declared a political agency in 1890. Captain MacIver was appointed first Political Agent to Zhob. However, tribesmen of Zhob always posed difficulties for the British government. In 1924, the British Political Agent to Zhob was murdered by tribesmen and during World Wars I and II military posts in the area were under continuos threat of attacks by the tribesmen.
Killa Saifullah has been home of the Jogizai family. After the submission of Shah Jahan, the Badshah of Zhob, to the British in 1888 at Gwal Haiderzai, Killa Saifullah area was annexed to Muslim Bagh (then Hindu Bagh) tehsil – established in 1890 – but later it was declared a sub-tehsil in 1893 and a tehsil in 1903. Muslim Bagh (formerly called Hindu Bagh) is believed to be named after a garden planted by a Hindu saint.
The district has some archaeological sites mainly attributed to the Mughals. The ruins of an old fort called Mughalo Killa or “the fort of the Mughals” were found to the west of the Karezgai village, about 3¼ kilometres from Muslim Bagh, below which there is a spring of water which was reopened about 125 years ago. Fragments of ancient pottery were found in these ruins and it is said that old silver and copper coins were also found. The ruins of a fort called Khanki lie near Shina Khura about 25 kilometres east of Muslim Bagh. Local tradition asserts that the fort was held by Miro, a Mughal governor, who was miraculously overthrown by Sanzar Nika, the progenitor of the Sanzarkhel Kakars. There are also ruins of an old fort called the Mughalo Brunj in Murgha Faqirzai. Similar ruins occur near Toiwar, Sharan, Ismailzai and on the Zhar hill near Akhtarzai. There also exist ancient karezes, said to have been made in Mughal times, which may be considered as relics of archaeological interest. These include Karez Akhtarzai, Karez Soghai and Mustafa Karez in Killa Saifullah sub-division and 2 karezes in Sra Khulla, about 6½ kilometres from Muslim Bagh.
The entire Killa Saifullah district remained a part of Zhob district as Upper Zhob sub-division up to 14th December 1988. However, Badinai, sub-tehsil of Killa Saifullah district, was previously included in Kakar Khurasan as sub-division of Zhob with the name Kashatoo. About two years ago it was transferred to Killa Saifullah district. At present, Killa Saifullah district comprises Killa Saifullah sub-division – including Killa Saifullah tehsil and Badinai sub-tehsil – and Muslim Bagh sub-division – including Muslim Bagh tehsil and Loiband sub-tehsil. Kan Mehterzai is a monumental place in the district where Asia’s highest railway station is located.