Ala-ud-din Khalji was the first Muslim sultan of the North who penetrated the Deccan in AD 1296, defeated the Yadavas and impoverished the dynasty by carrying away a huge booty. Malik Kafur, his lieutenant, completed his missions and, by 1310, Yadava rule came to an end.

Muhammad Tughluq (1324-1350), who extended his authority up to Madurai in the South, emulated Ala-ud-din Khalji’s example. However, his experiment of transferring his capital from Delhi to Daulatabad was a failure. The fall of the Tughluqs gave rise to a new Muslim power in the Deccan under the leadership of Sultan Ala-ud-din Hasan Bahamani in 1347, and the Bahamani dynasty lasted nearly 150 years. Deogiri, or Daulatabad, was for a while the capital of the Bahamanis. By the 16th century, the Bahamani kingdom was parcelled out into five independent regions - Qutb Shah (Golkonda), Nizam Shah (Admednagar), Imad Shah (Varhad), Adil Shah (Bijapur) and Barid Shah (Bidar), which included parts of Maharashtra. In order to preserve political authority, these Deccani Muslim rulers had to employ the local people in civil, military and diplomatic services. The Mughals annexed the provinces by the end of the 17th century.