For much of the first millennium CE the region was part of the territory of the Western Gangas, whose capital was at Talakadu on the Kaveri. Their inscriptions, including the Begur stone, are the earliest written records of the area.
Around the early 11th century the Cholas of Tamil Nadu pushed north and held the region for roughly a century. Chola-style temples survive in and around the city. The Someshwara temple at Begur and the older parts of several temples in Domlur and Madivala show their influence.
The Hoysalas drove the Cholas out in the early 12th century, and the area later passed to the Vijayanagara Empire in the 14th century. Local chieftains, the Yelahanka Nadaprabhus, governed on Vijayanagara's behalf. It was one of these chieftains, Kempegowda, who built the town we now call Bengaluru.
Further reading: Western Ganga dynasty on Wikipedia.