Shah was born into a distinguished family of Saadat (= Arabic plural of Sayyid) who had their ancestral home at Paghman, not far from Kabul.

[3][4] Her paternal grandfather, Sayyid Amjad Ali Shah, was the nawab of Sardhana, in the North-Indian state of Uttar Pradesh.

[5] The principality was awarded to his ancestor Jan-Fishan Khan during the British Raj, and had been ruled formerly by the Kashmiri-born warrior-princess, the Begum Samru.

[7] In that time she travelled widely, collecting stories and studying folklore.

Her travels took her through Africa and the Middle East, through the jungles of Sarawak, across the Australian Outback, Afghanistan, and beyond.