 In the turbulent regional politics of the time, Quli Qutb Shah ruler of Golconda Fort (in modern Hyderabad) was asserting his dominance and Shitab Khan had to face invasions from Golconda which was just shaking off the suzerainty of the Bahmanis.Warangal succumbed to the Golconda ruler and Shitab Khan had to flee, about 1512.He joined the service of Prataparudra Gajapati, King of Kalinga (Orissa).