Archaeologists have discovered evidence of human settlement in the Kōfu area dating to the Japanese Paleolithic period, with continuous settlement through the Jōmon, Yayoi and Kofun periods. During the Nara period, the provincial temple of Kai Province was established in what is now Kōfu, indicating that the Nara period provincial capital was located nearby, as the name of the city implies. During the Heian period, a branch of the Minamoto clan, the “Kai-Genji” ruled over vast "shōen" estates, and developed a military force noted for its use of cavalry. By the Muromachi period, a branch of the Kai-Genji, the Takeda clan came to dominate the area, and built a castle in what is now part of Kōfu.