By the late Vedic period, they ruled a kingdom located south of the Kurus, and west of the Yamuna river which separated it from the kingdom of the Panchalas. It roughly corresponded to the former state of Jaipur in Rajasthan, and included the whole of Hindaun, Alwar with portions of Bharatpur. The capital of Matsya was at Viratanagari (present-day Bairat) which is said to have been named after its founder king, Virata. In Pali literature, the Matsya tribe is usually associated with the Surasena. The western Matsya was the hill tract on the north bank of the Chambal River.
In the early 6th century BCE, Matsya was one the sixteen Mahajanapadas (great kingdoms) mentioned in the Buddhist text Anguttara Nikaya, but its power had greatly dwindled and it was of little political importance by the time of Buddha. The Mahabharata (V.74.16) refers to a King Sahaja, who ruled over both the Chedis and the Matsyas, which implies that Matsya once formed a part of the Chedi Kingdom.
Other than the Matsya kingdom to the south of Kuru Kingdom, which falls in the Hindaun and Alwar, Bharatpur districts of Rajasthan, the epic refers to as many as six other Matsya kingdoms. Upaplavya was a notable city of the kingdom.