We know very little about the early history of the Malls. It is quite difficult to trace the origin of the Mallas. Hoverer, the following references are worth mentioning:
1. It is said that Arideva was very fond of wrestling. Once, while he engaged himself in wrestling, he heard the news of the birth of a son to him. As the son was born to him at the time when he was wrestling, he added the word 'Mall' which means wrestling, after his name. From that time, the successors of Arideva used the word 'Malla' after their name, so it became the name of the dynasty.
2. The Mallas had their partly democratic form of government at Kushinagar, Pawa and in the neighbourhood of Baishali before the sixth century B.C.
3. Buddhist inscriptions tell us that Gautama Buddha explained the importance of the land of the Mallas to one of his disciples, Ananda.
4. From the inscriptions in the temple of Changunarayan, we learn that Manadeva led a campaign against Mallapuri, the land of the Mallas on the other side of the Gandaki river.
5. The Chalukyas and Pallavas of South India also used 'Malla' as their surname.
6. In the Lichchhavi inscriptions 'Mallakar' is mentioned which must have been a tax that the Mallas had to pay to the lichchavis or vice-versa.
All these reference show that there were people called Mallas from the very early days and the origin of 'Malla' was not invented by Arideva. While the Lichchhavis were ruling over the Nepal valley, there was a powerful kingdom of the Mallas across the Candaki river. It was called Malla puri. There was also a powerful Malla kingdom in Dullu, which lies in the west. The rise of the Mallas was held back by Manadeva, the powerful Lichchavi king. But, in course of time, they regained power and defeated the weaker Lichchhavi king of the Nepal valley. Though the word ' Malla' was not invented by Arideva, it was Arideva who used Malla as his surname for the first time in the history of Nepal. So, the credit for introducing 'Malla' gies to Arideva who is also known as Ari Malla. His followers were Abhay Malla, Jay Bhimdeva Malla, Devala Devi and Harisimsha Dev. Fayasthiti Malla, Yaksha Malla, Bhupatindra Malla, Siddhi Narasimha Malla, Pratap Malla and Jaya Prakash Malla were the most famous Malla kings of medieval period.