Surastras as a tribe existed at least as early as the period represented by the Epics. The tribe, together with its country, is mentioned in more than one connection in Valmlki's Ramayana. The Kiskindhya Kanda locates the tribe in the west. Surastras were included in the west division of India is upheld not only by a reference in the Mahabharata, where they are associated with the countries of the Kuntis and Avantis, but also by the evidence of the Puranas. According to the Vishnu Purana, they are definitely located in the extreme west, and associated with the Suras, Abhiras, Arbudas and Malavas, all of whom dwelt along the Paripatra Mountains. The Markandeya Purana includes them in West India (Aparanta), while the Brahma Purana associates them with the Aparantas, Sudras, Abhiras and Malavas, and describes them as dwelling along the Pariyatra hills. This geographical location of the tribe is also supported by the evidence of the Kavyamimamsa of Rajasekhara who includes the Surastra country in the Pashcaddesa or west division along with Dasoraka, Travana, Bhrgukaccha, Kacchiya, Anartta, Arbuda and other countries. At the time of the Mahabharata, the Surastra country was ruled by the Yadavas. Kautaliya has referred that Surastras followed a democratic form of government and it was implied by the Sanghas that existed among the Surastras.
The Surastra country is referred to in Baudhayana's Dharmasutra, where it is coupled with Daksinapatha (Deccan). The country came to be included in the Maurya Empire as early as the reign of Chandragupta. The region also had been under the dominion of Ashoka, the great Mauryan Empire. After Ashoka the kingdom of Surastras had passed into the hands of the Bactrain Greeks. It has also been said that after the Scythian occupation, Surastra seems to have passed into the hands of the Guptas. Historical references say that the kings of Surastra had to buy peace of their region by establishing diplomatic relations with Samudra Gupta. The rule of the Guptas in this territory does not seem to have long survived, soon the Maitrakas of Valabhi asserted their independence, and had established their supremacy over West Malwa, Baroda, Gujarat, Kathiawar and the adjoining region.
History states that when the Maitrakas of Valabhi became extinct about the middle of the eighth century A.D., the Surastras seem to have suffered a reverse at the hands of the Tajikas who are generally identified with the Arabs.