Mathura has an ancient history and also homeland and birthplace of Krishna who was born in Yadu dynasty. According to the Archaeological Survey of India plaque at the Mathura Museum, the city is mentioned in the oldest Indian epic, the Ramayana. In the epic, the Ikshwaku prince Shatrughna slays a demon called Lavanasura and claims the land. Afterwards, the place came to be known as Madhuvan as it was thickly wooded, then Madhupura and later Mathura.

In the 6th century BCE Mathura became the capital of the Surasena Kingdom. The city was later ruled by the Maurya empire (4th to 2nd centuries BCE). Megasthenes, writing in the early 3rd century BCE, mentions Mathura as a great city under the name Μέθορα (Méthora). It seems it never was under the direct control of the following Shunga dynasty (2nd century BCE) as not a single archaeological remain of a Shunga presence were ever found in Mathura. Mathura may have come under the control, direct or indirect, of the Indo-Greeks some time between 180 BCE and 100 BCE, and remained so as late as 70 BCE according to the Yavanarajya inscription, which was found in Maghera, a town 17 kilometres (11 mi) from Mathura. The opening of the 3 line text of this inscription in Brahmi script translates as: “In the 116th year of the Yavana kingdom…” or ‘”In the 116th year of Yavana hegemony” (“Yavanarajya”) However, this also corresponds to the presence of the native Mitra dynasty of local rulers in Mathura, in approximately the same time frame (150 BCE—50 BCE), possibly pointing to a vassalage relationship with the Indo-Greeks.

After a period of local rule, Mathura was conquered by the Indo-Scythians during the 1st century BCE. The Indo-Scythian satraps of Mathura are sometimes called the “Northern Satraps”, as opposed to the “Western Satraps” ruling in Gujarat and Malwa. After Rajuvula, several successors are known to have ruled as vassals to the Kushans, such as the “Great Satrap” Kharapallana and the “Satrap” Vanaspara, who are known from an inscription discovered in Sarnath, and dated to the 3rd year of Kanishka (c. 130 CE), in which they were paying allegiance to the Kushans. Mathuran art and culture reached its zenith under the Kushan dynasty which had Mathura as one of their capitals, the other being Purushapura (modern-day Peshawar, Pakistan).

Faxian mentions the city as a centre of Buddhism about 400 CE while his successor Xuanzang, who visited the city in 634 CE, mentions it as Mot’ulo, recording that it contained twenty Buddhist monasteries and five Brahmanical temples. Later, he went east to Thanesar, Jalandhar in the eastern Punjab, before climbing up to visit predominantly Theravada monasteries in the Kulu valley and turning southward again to Bairat and then Mathura, on the Yamuna river.

The city was sacked and many of its temples destroyed by Mahmud of Ghazni in 1018 CE and again by Sikandar Lodhi, who ruled the Sultanate of Delhi from 1489 to 1517 CE. Sikander Lodhi earned the epithet of ‘Butt Shikan’, the ‘Destroyer of Hindu deities’. The Mughal Emperor Aurangzeb, built the Shahi-Eidgah Mosque during his rule, which is adjacent to Shri Krishna Janmabhoomi believed to be over a Hindu temple.