I was searching this for a long time, but never seriously enough. Madala Panji is the name of the chronicle maintained by Puri Jagannatha Temple. It contained a list of kings who ruled Orissa from time immemorial. Only after you reach medieval age, there is a semblance of practicality in dates. While Yudhistira is considered as the first king, Parikshit’s and Janamejeya’s reigns were longer than what Mahabharata says.
If there is any truth in Asoka’s invasion of Kalinga, it is possible that Yayati Kesari is Kharavela who brought back the Jain idol from Magadha(here, it is mentioned as that of Jagannatha), though the dates don’t match. However, one should note one thing – this list is not of the kings of Kalinga. It is of the kings who ruled Puri. It can be a petty ruler for all it means.
Though Puranas talk about the dynastic lines, they list out in details, only the dynasties which ruled Magadha. That raises an interesting question, whether Srimukha was the first Satavahana ruler or the first Satavahana ruler who ruled Magadha. All those things are beyond the discussion.
The main thing is, we need to be more focussed in bringing such data out, which lists out the rulers and details regarding them, ruling not so prominent areas in Indian polity. The four main ones I can think of, Kalhana’s Rajatarangini, Madala Panji of Puri, the royal chronicles of Tripura and Manipur.
The king list below(Appendix I, A History of Orissa by WW Hunter) is taken from Babu Bhabanicharan Bandopadhyaya’s Purushottama Chandrika which is based directly on Madala Panji. It’s a very interesting thing to note that not one ruler is named Jagannatha in the list of 100+ rulers who ruled 5000 years. Also to note is that, how did they come up with the date for Yudhistira. What was the basis for that date?

Start End Name Comments
3101 3089 Yudhistir Lunar Race of Delhi, of Mahabharata fame
3089 2358 Parikshit
2358 1807 Janamejeya
1807 1407 Sankar Deva
1407 1037 Gautam Deva Extended the Kingdom of Orissa to Godavari
1037 822 Mahendra Deva Founded the town of Rajamahendri as capital
822 688 Ishta Deva
688 538 Sevak Deva
538 421 Bajra Deva Orissa was invaded by Yavanas from Marwar, Delhi, Babul Desh(Iran?), Kabul. Repulsed
421 306 Narsinh Deva Faced a northern invasion which he beat back. Reduced a great part of Delhi kingdom. Excavated the tank of Dantan near Jaleshwar
306 184 Mankrishna Deva Faced a Yavana invasion from Kashmir which he beat back
184 57 Bhoi Deva Faced a Yavana invasion, beat back. Reduced all India
57 78 Vikramaditya & Sakaditya Vikramaditya became a master of whole India but was killed by a South Indian Salivahana. Sakaditya followed him
78 143 Karamjit Deva
143 194 Hatkeshwar Deva
194 237 Bir Bhuvan Deva
237 282 Nirmal Deva
282 319 Bhim Deva
319 323 Sobhan Deva Yavana invasion and conquest of Orissa under Raktabahu. He was overwhelmed by the sea which advanced to form Chilika. Sobhan Dev escaped with the idols of Jagannatha and his siblings and buried them in a cave at Sonpur. He died in the forests
323 328 Chandra Deva Yavana puppet. Executed by Yavanas
328 474 Yavana Occupation of Orissa
474 526 Yayati Kesari Expelled the Yavanas, formed the Kesari Dynasty. Brought back the idol of Jagannatha, started the temple to Siva at Bhubaneswar. He ruled from Jajpur
526 583 Surya Kesari
583 623 Ananta Kesari
623 677 Alabu Kesari
677 693 Kanak Kesari
693 701 Bir Kesari
701 706 Padma Kesari
706 715 Briddha Kesari
715 726 Bata Kesari
726 738 Gaja Kesari
738 740 Basanta Kesari
740 754 Gandharva Kesari
754 763 Janamejeya Kesari
763 778 Bharat Kesari
778 792 Kali Kesari
792 811 Kamal Kesari
811 829 Kundal Kesari Built the temple of Markandeshwar in Puri
829 846 Chandra Kesari
846 865 Bir Chandra Kesari
865 875 Amrita Kesari
875 890 Bijaya Kesari
890 904 Chandrapal Kesari
904 920 Madhusudhan Kesari
920 930 Dharma Kesari
930 941 Jana Kesari
941 953 Nripa Kesari Founded Cuttack
953 961 Makar Kesari Constructed a revetment to protect Cuttack from inundation
961 971 Tripura Kesari
971 989 Madhav Kesari
989 999 Gobinda Kesari
999 1013 Nritya Kesari
1013 1024 Narsinh Kesari
1024 1034 Kurma Kesari
1034 1050 Matsya Kesari Built the great bridge at Atharanala, at the entrance to Puri
1050 1065 Bahara Kesari
1065 1078 Baman Kesari
1078 1080 Parasu Kesari
1080 1092 Chandri Kesari
1092 1104 Salini Kesari His queen built the Natya Mandira at the Temple of Bhubaneswar
1104 1107 Puranjan Kesari
1107 1119 Vishnu Kesari
1119 1123 Indra Kesari
1123 1132 Suvarna Kesari Died childless and was succeeded by Chodaganga,a king from South. Alternate view is, he was killed in an invasion by Chodaganga who was instigated by an exiled officer Basudeva Bahanpati
1132 1152 Chodaganga Founder of Ganga Vamsa
1152 1166 Gangeswar Extended the Kingdom of Orissa from Ganga to Godavari. Had five royal cities – Jajpur, Chaudwar, Amravati, Chatna and Varanasi(Cuttack). Excavated a tank Kausalya Ganga between Pippli and Khurdha
1166 1171 Ekjatam Deva
1171 1175 Madan Mahadeva
1175 1202 Ananga Bhima Deva One of the greatest kings of Orissa. Built the current Jagannatha Temple
1202 1237 Rajarajeshwara Deva
1237 1282 Langula Narasimha Built the Konark Sun Temple
1282 1307 Kesari Narsinh Filled up the river Balagandi which ran between the temple anf the country house of Jagannatha and obstructed the Rathas
1307 1327 Pratap Narsinh
1327 1329 Gatikanta Narsinh
1329 1330 Kapil Narsinh
1330 1337 Sankha Bhasur
1337 1361 Sankha Bhanudeva
1361 1382 Bali Basudeva
1382 1401 Bir Basudeva
1401 1414 Kali Basudeva
1414 1429 Nengatanta Basudeva
1429 1452 Netra Basudeva
1452 1479 Kapilendra Deva A common herdbuy tending flocks of his Brahmin master, raised to the throne later
1479 1504 Purushottamadeva The King of Kanchipuram refused to marry his daughter to Purushottamadeva stating that Orissa Dynasty holds the office of Sweeper to Jagannatha. Purushottama invaded Kanchi and carried off his daughter. The officer entrusted with this presented the princess to the king when he was sweeping in the Ratha Yatra
1504 1532 Prataparudra Deva The reign was disturbed by successive dominations of Buddhists and Brahmins and persecutions of the rulers before a semblance of stability was achieved when the king converted to Vaishnavism under Chaitanya Mahaprabhu. Extended his forces till Kanyakumari, faced Afghan invasion which plundered Puri, idols carted off to safety beforehand
1532 1533 Kaluya Deva Murdered by the Prime Minister Gobinda Bidyadhar
1533 1534 Katharuya Deva Last of the Gangas. Assassinated by Gobinda Bidyadhar
1534 1541 Gobinda Bidyadhar Disputes with Muslims led to loss of Rajamahendri
1541 1549 Chakra Pratap
1549 1550 Narsinh Jena
1550 1551 Raghuram Chhotra
1551 1559 Telinga Mukunda Deva Last of the independent kings of Kalinga. Constructed a Ghat on Hughli at Tribeni. Kalapahar, the general of the Muslim king of Bengal invaded, defeated and killed Mukundadeva outside the walls of Jajpur
1559 1578 Interregnum Anarchy for 19 years. The Afghan Governor of Orissa, Daud Khan invaded Bengal but faced a counter invasion from Mughals under Munim Khan
1578 1607 Ramachandra Deva Son of a previous Prime Minister of Orissa. Appointed and confirmed by Todar Mal. Faced troubles from a rival claimant, Man Singh settled the issue by granting some forts to the rival
1607 1628 Purushottamadeva Killed in Battle. From then on, they were simply called Rajas of Khurda
1628 1653 Narsinh Deva Faced an invasion from South under Shahbaz. Had to buy peace. He brought the idols of Sun and Moon to Puri from Konark
1653 1654 Gangadhar Deva
1654 1662 Balabhadra Deva
1662 1690 Mukunda Deva
1690 1713 Dibya Sinh Deva
1713 1718 Krishna Deva
1718 1725 Gopinath Deva
1725 1736 Ramachandra Deva
1736 1773 Bir Kishor Deva Habib Khan, a general under the Marathas annex the province but Marathas restore it back. In 1753, Marathas invade again and capture Orissa
1773 1791 Dibya Sinh Deva
1791 1810 Mukunda Deva British occupation of Orissa by expulsion of Marathas in 1803. The next year, a prince of the family rebels in Khurda. He was defeated and captured, arrested in Cuttack and Midnapur, later allowed to retire to Puri
1810 1857 Ramachandra Deva
1857 1871 Dibya Sinh Deva