Malla Kingdom was situated in the Gangatic plain between the Kosala and Videha. The epic Mahabharata speaks about a Malla conquered by the Pandava Bhima during his military campaign through the eastern kingdoms to collect tribute for King Yudhishthira's Rajasuya sacrifice.
Bhima defeated the virtuous and mighty king Dirghayaghna of Ayodhya. And then he subjugated the country of Gopalakaksha and the northern Kosalas and also the king of Mallas. And the mighty one, arriving then in the moist region at the foot of the Himalayas soon brought the whole country under his sway. He next conquered the country of Bhallata, as also the mountain of Suktimanta that was by the side of Bhallata. Then Bhima vanquishing in battle the unretreating Suvahu the king of Kasi, brought him under complete sway. Then he overcame in battle, by sheer force, the great king Kratha reigning in the region lying about Suparsa. Then the hero of great energy vanquished the Matsya (Eastern Matsyas) and the powerful Maladas and the country called Pasubhumi that was without fear or oppression of any kind. And Bhima then, coming from that land, conquered Madahara, Mahidara, and the Somadheyas, and turned his steps towards the north. And the mighty son of Kunti then subjugated, by sheer force, the country called Vatsabhumi, and the king of the Bhargas, as also the ruler of the Nishadas and Manimat and numerous other kings. Then Bhima, with scarcely any degree of exertion and very soon, vanquished the Southern Mallas and the Bhagauanta mountains.
Surrounding the kingdom of the Kurus, are, many countries beautiful and abounding in corn, such as Panchala, Chedi, Matsya, Surasena, Pattachchara, Dasarna, Navarashtra, Malla, Salva, Yugandhara, Saurashtra, Avanti, and the spacious Kuntirashtra.
Quickly send word to Salya, and to the kings under him, and to king Bhagadatta of immeasurable valour residing on the eastern sea-coast, and to fierce Hardikya, and Ahuka, and the king of the Mallas of powerful understanding, and Rochamana.
.....the Goparashtras, and the Karityas; the Adhirjayas, the Kuladyas, the Malla-Rashtras, the Keralas, the Varatrasyas, the Apavahas.....