The founder of Nayakship in Madurai was Viswanatha Nayaka. He was the son of Nagama Nayaka, a supervisor of the administration of the southern districts under the well known ruler of Vijayanagar, Krishnadeva Raya.

Viswanatha entered the service of Krishnadeva Raya as his betel-bearer. Owing to loyalty and bravery, he soon, became one of his personal attendants. Viswanatha accompanied Krishnadeva Raya in his expedition against the king of Orissa. Looking at Viswanatha`s valor Krishnadeva Raya appointed him as the commander of a battalion. Viswanatha then captured Raichur in 1520. Nagama Nayaka disobeyed Krishnadeva Raya and Viswanatha was sent to control his own father. Nagama was defeated and was taken to Vijayanagar as a captive, but was pardoned by Krishnadeva.

Later, Viswanatha was appointed as viceroy of the south with the titles `Chief of Pandya Country` and `Lord of the Southern Throne`. Viswanatha Nayaka was a good administrator and was ably assisted in his work by Ariyanatha, his Dalavay and Pradhani, and Kesavappa Nayaka. Viswanatha with great tact improved the defense of the cities of Madurai and Tiruchi. He renovated the great temple of God Sundareshwara (Siva) and Goddesses Minakshi at Madurai. One of Viswanatha`s memorable works was the organization of the Madurai country into palaiyams and the chiefs of these divisions were called palayakkarar or poligar. It is said that 72 such palaiyams were created and that each palaiyajjar was left in charge of one of the 72 bastions of the Madurai fort. Ariyanatha suppressed a rising of five Pandyas in the region of Kaitar in Tirunelveli and restored order. Viswanatha ruled till 1564 and remained loyal and subordinate to Vijayanagar rulers.