The Matsyas have been mentioned in several historical records along with other tribes namely the Usinaras, Kuru-Panchalas, and Kail-Videhas. In the Gopatha Brahmana, they are connected with the Salvas, a Kshatriya tribe in their neighbourhood, and are mentioned along with other well-known Kshatriya tribes of the Vedic period, such as the Kuru-Panchalas, Anga-Magadhas, Kasi-Kosalas and Vasa-Usinaras. The relation of the Matsyas with the Salvas has also been attested by the Mahabharata. In the Padma Purana and the Vishnu Purana the Matysyas have been mentioned as one of the Janapadas of Bharatavarsa. In the Bhisma Parva of the Mahabharata, the Cedi-Matsya-Karusas, Matsya-Karusas, Cedi-Panchala-Karusa-Matsyas, Matsya-Panchala-Cedis, Cedi-Karusa-Matsyas, and Cedi-Matsyas have been grouped together.
History says that Matsyas were regarded by the Indians as belonging to the most orthodox followers of Brahmanism in ancient times. In fact the Matsyas occupied a pre-eminent position both because of the purity of their conduct and customs, and through their bravery and prowess on the battle field of Kurukshetra. It has also been said that during the time of Ramayana the Matsyas were not regarded as important people perhaps they had lost the importance which they had acquired in the Vedic age.
Even in the Buddhist literature there has been ample mention of the Matsyas. In the Shatapatha Brahmana there has been mention of a Matsya King Dhvasan Dvaitavana. Manu has said that Matsya country formed a part of the Brahmarsi-desa that is the country of the holy sages. In later times the Matsya country appears to have been known also as Virata or Vairata.
The capital of the country of the Matysya was generally called Viratanagara in the Virdtaparvan and sometimes was also called Matsyanagara. Another important city of the Matysyas was Upaplavya. Evidently it was this Viratanagara which afterwards came to be known as Vairat. It was the city which had the royal seat of the epic king Virata, the friend of the Pandavas.
It has been referred in several places of history that the Pandava brothers had completed their period of exile in the kingdom of the Matsyas and when king Virata of Virat was captured it was Bhima, the second Pandava brother who had rescued him and after the exile of the Pandavas ended the marriage of Abhimanyu, son of Arjuna, and Uttara, daughter of King Virata, was arranged and celebrated with great pomp.
Kautaliya has said in his account that that the monarchical constitution lasted throughout the period of Matsya's independence. The kingdom was probably annexed at one time by the neighbouring kingdom of Cedi, and was finally absorbed into the Magadhan Empire.