It has been said in history that ancient Madura was same as the present day Mathura. The epic tradition says the Pandus of Indraprastha were closely connected with the ruling family of the Surasena country by ties of friendship and marriage. Some historians have noted that the Pandyas of the south were closely associated with the Pandus of the north and the Surasenas of Mathura. In the great epic Mahabharata it has been mentioned that Sahadeva, the youngest of the Pandu princes, is represented in his career of conquest to have gone to Daksinapatha after having conquered the king of the Pandyas. In the same way the country of the Pandyas is mentioned in the Ramayana where Sugriva is said to have sent his monkey-soldiers in quest of Sita, Lord Rama's consort. In the Indian Puranas also as in the case of the Markandeya Purana, Vayu Purana and Matsya Purana there is mention of the Pandyas as a tribe. Emperor Ashoka in his rock edicts had mentioned that the kingdom of the Pandyas fell outside the purview of his empire.
Historical account like the account of Vijaya states that there existed a matrimonial alliance between the ruler of Lanka and that of Pandya. It has also been mentioned that there was a very early settlement in Ceylon of skilled craftsmen and families of the eighteen guilds, all from Pandya. From several historical records it has also been found out that Nedun-jeliyan II was the first conspicuous Pandya ruler who made the Pandyas the leading power of the south. But the supremacy of the south ultimately passed to the Pallavas.