โตเกียวแต่เดิมเป็นหมู่บ้านประมงเล็ก ๆ ที่ชื่อเอโดะ ต่อมาใน ค.ศ. 1457 ปราสาทเอโดะได้ถูกสร้างขึ้น และต่อมาในปีทศวรรษที่ 1590 เป็นยุคที่โทกูงาวะ อิเอยาซุได้เริ่มปราบหัวเมืองต่าง ๆ ซึ่งภายหลังจากปราบหัวเมืองต่าง ๆ ลงได้อย่างราบคาบแล้วใน ค.ศ. 1603 เขาได้สถาปนารัฐบาลโชกุนขึ้นปกครองประเทศ โดยมีเอโดะเป็นที่ตั้งของ "บากูฟุ" (รัฐบาลทหาร) และสถาปนาตนขึ้นเป็นโชกุน เมืองเอโดะจึงได้กลายเป็นศูนย์กลางของรัฐบาลทหารของเขาซึ่งมีอำนาจปกครองทั้งประเทศ ในช่วงเวลาต่อมาในยุคเอโดะ เมืองเอโดะก็ขยายตัวขึ้นจนกลายเป็นเมืองที่ใหญ่ที่สุดเมืองหนึ่งในโลก โดยมีประชากรมากกว่า 1 ล้านคนใน คริสต์ศตวรรษที่ 18[9] และเป็นที่ยอมรับว่าเป็นเมืองหลวงของญี่ปุ่น[10] แม้ว่าองค์จักรพรรดิประทับอยู่ในนครหลวงเฮอังเกียว (เกียวโต)

หลังจากนั้นประมาณ 263 ปี ระบอบปกครองภายใต้โชกุนถูกล้มล้างโดยการปฏิรูปเมจิ อำนาจการปกครองจึงกลับคืนมาสู่จักรพรรดิอีกครั้งใน ค.ศ. 1869 จักรพรรดิเมจิทรงย้ายเมืองหลวงมาที่เอโดะและเปลี่ยนชื่อเมืองเป็นโตเกียว โตเกียวจึงกลายเป็นศูนย์กลางทางการปกครองและวัฒนธรรมของประเทศ [11] และการที่จักรพรรดิทรงย้ายมาประทับจึงทำให้โตเกียวกลายเป็นเมืองหลวงอย่างเต็มตัวและปราสาทเอโดะเปลี่ยนเป็นพระราชวังหลวง

ในยุคเมจิ โตเกียวมีการพัฒนาโดยได้รับอิทธิพลจากตะวันตก เช่น การเปิดบริการโทรเลขระหว่างโตเกียวกับโยโกฮามะ ในปี 1869 และการเปิดบริการรถไฟสายแรกระหว่างชิมบาชิและโยโกฮามะในปี ค.ศ. 1872[11]