A Rajput dynasty was ruling in Kherla before the Gonds. The greatest of those Rajput rulers was named Jaitpal, who is credited with building the fortress of Kherla. Jaitpal was succeeded by Narsingh Rai, the first Gond ruler of Kherla. During his reign, the kingdom stretched in a westerly direction to the hills north of Berar, including the fortress of Gawilghur. His reign was marked by constant warfare with the Muslim rulers to his north and south.
Firuz Shah Bahmani, the ruler of the Bahmani Sultanate, invaded his domain and laid siege to the fortress of Kherla. He captured Narsingh Rai's eldest son and the Gond ruler, with his power reduced, went to Firuz Shah Bahmani's camp at Ellichpur with his family.[1] He showed remorse for his actions, and was recognized as the Bahmani Sultan's vassal. He was to pay a fixed tribute every year and one of his daughters was married into Firuz Shah's harem as a political move.[4]
As a consequence of his alliance with the Bahmani Sultanate, Hoshang Shah, the ruler of Malwa Sultanate became hostile towards Narsingh Rai. Hoshang Shah repeatedly attempted to take Kherla as his invite of alliance had been refused by Narsingh Rai. For a brief period the tables were turned as the Gond king pursued Hoshang's army when they were retreating across the hilly country of Kherla from an unsuccessful campaign in the Deccan and slaughtered the soldiers. Next, when Ahmad Shah, the Bahmani ruler and Narsingh Rai's ally was campaigning in Gujarat, Hoshang jumped upon this opportunity and attacked Kherla once again. In the following battle, Narsingh Rai was slain and Kherla remained in the Malwa sultan's control for some time.[2][1]
