Das Gebiet um die heutige Stadt war nach archäologischen Funden bereits zur Jōmonzeit (um 7500 v. Chr.) besiedelt. 1457 gewann mit dem von Ōta Dōkan (* 1432, † 1486), einem Vasallen der das Gebiet beherrschenden Uesugi-Sippe, begonnenen Bau der Burg Edo (Edo-jō) das am Rand der Musashi-Ebene angelegte Dorf