Prolaya Nayaka, the first of the Musunuri leaders, understood that he could not meet the Sultanate in open battle. Instead, he chose the terrain that favored the outnumbered: the dense forests around Rekapalle, at the edge of the Papikondalu hills in the Eastern Ghats. From this stronghold, he controlled the narrow Sabari River valley and could obstruct traffic on the Godavari River as it passed through the hills. The Konda Reddis, indigenous hill communities who populated the surrounding forests, became his allies. Prolaya Nayaka first drove Sultanate forces from Rajahmundry, then seized control of the territory between the Krishna and Godavari rivers. In 1330, he issued the Vilasa Grant, a copper-plate inscription near Pithapuram, in which he described the devastation the northern armies had inflicted on the Telugu country and presented himself as the restorer of order. The language is raw with grief -- and with purpose.

Prolaya Nayaka died without children, and leadership passed to his cousin Kapaya Nayaka around 1333. Where Prolaya had been a guerrilla fighter, Kapaya proved to be a coalition builder. According to the Kaluvacheru Grant of 1423, he assembled a remarkable alliance of 75 Nayaka chieftains -- each commanding their own forces, each with their own territorial ambitions, but united in their opposition to Tughluq rule. Kapaya also reached beyond the Telugu country for help, approaching the Hoysala ruler Veera Ballala III in the south. Ballala agreed to provide military assistance. The timing was fortunate: Sultan Muhammad bin Tughluq, who had taken the Delhi throne in 1324, was simultaneously facing rebellions in Bengal, Madurai, and the Ganga-Yamuna plain. When he marched into the Deccan in 1334 to reassert control, an epidemic devastated his army, killing perhaps a third of his soldiers and leaving the Sultan himself gravely ill. He retreated to Delhi, and the Deccan was suddenly open.

In 1336, Kapaya Nayaka and his coalition struck. The Sultanate governor Malik Maqbul -- ironically a former Kakatiya commander who had converted and taken a new name -- found himself unable to hold the capital against the combined forces of the Nayaka alliance. He fled to Delhi. Historian R. C. Majumdar later characterized the event as a "national revolt" backed by a regular army, not merely a local uprising. Kapaya Nayaka took control of Warangal and a wide territory across eastern Telangana. He continued using the Kush Mahal, the audience hall built by the Sultanate rulers within the fort, and in a gesture that reveals the complexity of medieval Indian identity, he adopted the Persianized title "Sultan of the Andhra country." He was a Shaivite Hindu who claimed divine appointment by Shiva to protect dharma, ruling from a Muslim-built palace with a Muslim-derived title. History is rarely tidy.

Coalitions built on a common enemy tend to fracture once that enemy retreats, and the Nayaka alliance was no exception. Kapaya Nayaka's efforts to support other rebels in the region backfired when he aided Alauddin Bahman Shah, who then turned on him. The Bahmani Sultanate, now rising as a regional power, engaged Kapaya in a series of military contests over several years, gradually stripping away forts and territories, including Golconda near modern Hyderabad. In 1361, weakened and negotiating from a position of diminishing strength, Kapaya gifted the Turquoise Throne of Warangal to Bahmani Sultan Mohammed Shah I as part of a treaty. His own allies sensed vulnerability. In 1368, the Recherla Nayakas killed Kapaya in battle at Bhimavaram, near Warangal. With his death, the other allied Nayakas returned to their own towns, and the Musunuri chapter ended. But the thirteen years of restored rule had proven something that the region would remember for centuries: foreign domination was not inevitable.