Tokyo asalnya merupakan perkampungan perikanan kecil yang bernama Edo. Pada tahun 1457, Ōta Dōkan membina Istana Edo. Pada tahun 1590, Tokugawa Ieyasu berpangkalan di Edo, dan sebaik sahaja menjadi shogun pada tahun 1603, bandar ini menjadi pusat pentadbiran tenteranya untuk seluruh negara. Pada zaman Edo, Edo menjadi salah sebuah bandaraya terbesar di dunia dengan jumlah penduduk mencapai sejuta orang menjelang abad ke-18.[6]

Edo menjadi ibu negara de facto di Jepun[7] sungguhpun maharaja bersemayam di Kyoto, ibu kota diraja. Selepas kira-kira 263 tahun, kerajaan shogun digulingkan di bawah bendera pemulihan pemerintahan maharaja. Pada tahun 1869, ketika Maharaja Meiji pindah ke Edo pada usia 17 tahun, Tokyo sudah menjadi pusat politik dan kebudayaan negara,[8] kemudian dijadikan ibu kota diraja de facto oleh istana di samping bekas Istana Edo menjadi Istana Diraja. Bandaraya Tokyo ditubuhkan lalu kekal sebagai ibu negara sehingga taraf perbandarannya dimansuhkan pada tahun 1943 untuk digabungkan dengan "Wilayah Metropolitan" Tokyo.

Malangnya, Tokyo mengalami dua malapetaka hebat pada abad ke-20, tetapi mujurlah ia sempat pulih daripada kedua-duanya. Yang pertama ialah gempa bumi besar Kantō 1923 yang menyebabkan 140,000 penduduk maut atau hilang,[9] dan yang kedua ialah Perang Dunia Kedua, ketika Tokyo dibedil bertubi-tubi pada tahun 1944 dan 1945, menyebabkan 75,000 hingga 200,000 orang terbunuh dan separuh bandaraya musnah, lebih kurang sedahsyat jumlah kesan pengeboman Hiroshima dan Nagasaki.[10]

Selepas perang, Tokyo dibina semula sepenuhnya, dan berkilauan di mata dunia ketika Sukan Olimpik Tokyo 1964. Zaman 1970-an menyaksikan pembangunan bertingkat tinggi seperti Sunshine 60, pembinaan lapangan terbang baru yang berkontroversi[11] di Narita (yang agak jauh dari sempadan bandaraya) pada tahun 1978, dan jumlah penduduk meningkat kepada kira-kira 11 juta (dalam lingkungan kawasan metropolitan).

Rangkaian kereta api bawah tanah dan komuter Tokyo menjadi antara yang tersibuk di dunia[12] kerana semakin ramai orang yang berpindah ke kawasan Tokyo. Pada 1980-an, harga harta tanah melangit dalam gelembung hartanah dan hutang. Setelah gelembung itu meletup pada 1990-an, banyak syarikat, bank, dan orang ramai didapati berhutang gadai janji di sebalik kejatuhan nilai harta tanah, sehingga disusuli kemelesetan besar yang menjadikan 1990-an sebagai "sedekad hilang" di Jepun[13], tetapi kemudian beransur-ansur pulih.

Projek penebusgunaan tanah di Tokyo juga berterusan selama berabad-abad lamanya, terutamanya di kawasan Odaiba yang dijadikan kawasan beli-belah dan hiburan utama.