Scholars have constructed the political history of the ancient Pandya country based on the classical works such as Purananuru, Pattu paatu and Padirrupattu. Even though these works don’t throw much light on the exact timelines of each king and their reign, they are considered trustworthy accounts that present facts as they occurred.
The first Pandyan king who has been mentioned in the Sangam works recovered so far is Nedunj Cheliyan I, who ruled from the coastal town of Korkai, at the mouth of river Tamraparni. During this time, the Tamil country consisted of several small kingdoms ruled over by independent chieftains, in addition to the three monarchies of Cheras, Cholas and Pandyas. In a bid to expand his territory, Nedunj Cheliyan I invaded the kingdom of Kudal (later renamed Madurai), which was under the rule of an independent chieftain, Akutai. He defeated Akutai and moved the capital of Pandyan kingdom to Madurai. This king also defeated an invading army from the Deccan and hence was called Aariyap Padaikadantha Pandyan or the king who conquered the Aryan army. He was succeeded by his son Pudappandiyan, who expanded the kingdom by conquering Ollaiyur (near modern day Pudukkottai) – an act that earned him the name Ollaiyur thantha Pudappandian. Both Pudappandiyan and his predecessor, Nedunj Cheliyan I, were poets themselves who contributed to the Purananuru collection.
The successor of Pudappandiyan was Nedunj Cheliyan II also known as "Pasumpun Pandyan." Immediately after ascending the throne, he marched with his troops to the north of Vaigai and defeated the chieftain Evvi II. He then headed west and captured the Aayi territory controlled by another chieftain, Atiyan. Both Evvi II and Atiyan were made commanders of the Pandyan army for his battles against Kongu country that was further west. From here he expanded the Pandyan kingdom almost to the western coast, which earned him the title Vidambalamba Ninra Pandyan (the Pandyan whose kingdom was washed by two seas). Since he was responsible for expanding the Pandyan kingdom by annexing several kingdoms, he was also called Pannadu thantha Pandyan (the Pandyan who annexed many lands). His successor, Mudukudumi Peruvaludhi, was also a great warrior and carried the devastation into enemy territories. He performed yagas with the aid of Brahmin priests, similar to the tradition in northern India at that time.
The next king in the hierarchy was Nedunj Cheliyan III, who is considered the greatest of all the early Pandyan kings. Since the Pandyan kingdom was considerably larger than a few generations ago, he had to defend it against many neighbors invading from various fronts. Not only did he succeed in defending his territory, he also seems to have advanced into the enemy territories – the southern province of Cholas and eastern province of the Cheras. At one point, it is said that a coalition of his neighbors including the Cheras, Cholas and five other kingdoms, met him at a pitched battle in Talaialanganam, in present day Tanjore district. Nedunj Cheliyan emerged victorious in the battle that ensued and ended up annexing several new territories to his kingdom. He thus came to be known as Talaialanganathu Seruvendra Pandyan. The genealogy after this king is not very clear but there are at least four other kings who are thought to have ruled in the immediate succeeding generations. Notable among them were, Musiri Mutriya Cheliyan for the fact that he conquered the town of Musiri on the coast of the Arabian Sea and Ukkirap Peruvaludi for the fact that it was in his court that the famous poet Tiruvalluvar submitted his much-acclaimed work Tirukkural.