The term Pandya means ‘very Old'(பண்டைய) as against Cholas who were classified as new.
The Pandyas were in close liaison with the Pandavas of the Mahabharata.
Pandyan Kings took part in the Mahabharata War .(Karna Parav 20.25)
Arjuna and Krishna married Pandyan princesses and had children through them.
During the period of Ramayana, Sugriva advises his monkeys to search for Sita in the Kingdoms of Chera, Chola and Pandyas.
And, O Yudhishthira, in the country of the Pandyas are the tirthas named Agastya and Varuna! And, O bull among men, there, amongst the Pandavas, is the tirtha called the Kumaris. Listen, O son of Kunti, I shall now describe Tamraparni. In that asylum the gods had undergone penances impelled by the desire of obtaining salvation. In that region also is the lake of Gokarna which is celebrated over the three worlds, hath an abundance of cool waters, and is sacred, auspicious, and capable, O child, of producing great merit. That lake is extremely difficult of access to men of unpurified souls. Mahabharatha 3:88
And similarly, Pandya, who dwelt on the coast-land near the sea, came accompanied by troops of various kinds to Yudhishthira, the king of kings. Mahabharatha 5:19
Steeds that were all of the hue of the Atrusa flower bore a hundred and forty thousand principle car-warriors that followed that Sarangadhwaja, the king of the Pandyas. Mahabharatha 7.23.
References abound in Tamil Classics about the relationship between Sanatana Dharma and the Tamil Kings.
First reference of the Pandyas is the Parantaka Pandya who fought with Karikal Chola.
The Forty Kings mentioned before Karikala are not found to be recorded.
Yet references are found in the Ithihasa and Puranas about the Pandyas.
My inference is that Pandya Kingdom at Then Madurai then, was swallowed by a Tsunami and records might have been lost.
One surviving record is that Ravana signed a Peace Treaty with a Pandya King.
Please read my Post on this.
So, both the Chola and Pandya Dynasties date back to Ramayana period, if not earlier, for there are refernces in the Vedas about Tamil Nadu spices.
Probably Cholas and Pandyas belong to the same Family Tree of Manu, albeit descended from Cousins.
* Post On Chea Kings Follows.