Japonya'nın tarihî eyaletlerinden Owari Eyaleti'nin Aichi ilçesinde 16. yüzyılın başlarında Imagawa Ujichika Yanagi-no-maru olarak yapıldığı ve Nagoya-jō (那古野城) olarak anıldığı, 1532 ya da 1538'de Oda Nobuhide tarafından Imagawa Ujitoyo'nun elinden alındığı ve Oda Nobuhide'nin oğlu Oda Nobunaga'nın kalede doğduğu düşünülmektedir.

1555'te Oda Nobunaga Kiyosu Kalesi'ne taşındığı için iptal edildi.

Edo döneminde 1609'da Tokugawa Ieyasu dokuzuncu oğlu Tokugawa Yoshinao için Eski Nagoya Kalesi'nin arazisinde yeni bir kaleyi yaptırmasına karar verdi ve Tenkabushin (Daimyoların mali gücünü azarmak amacıyla yaptırılan inşaat işleri)'in çerçevesinde Batı Japonya'daki daimyolara yaptırdı.

1612 - 1617 yılları arasında çevresindeki şehri ve şehirliler ile birlikte Kiyosu Kalesi'nden Nagoya Kalesi'ne taşındı Buna "Kiyosugoshi" denir. Nagoya Kalesi Edo dönemi boyunca "Gosanke" (Tokugawa klanının üç büyük ailesi)'nin birincisi Owari Tokugawa ailesinın Shiro'su olarak kullanıldı.

28 Ekim 1891 tarihinde Mw ölçeğine göre 7,5 büyüklüğünde gerekçeleşen Nobi Depremi'nde Honmaru Nansei Gurō (Baş Kulesi'nin batıgüney köşe kuleciği) ve Tamon Gurō (Tamon Kulecik) yıkıldıysa da Honmaru Sarayı ve Tenshu ise dayandı.

Meiji Devrimi'nden sonra iptal edildi ve Owari Tokugawa ailesinin 17. reisi Tokugawa Yoshikatsu, Nagoya Kalesi'nin yıkılışı ve Shachihoko'nun devlete armağan edilişini önerdi. Fakat Prusya Krallığı Tokyo Elçisi Maximilian August Scipio von Brandt ve dönemin Japon İmparatorluk Kara Kuvvetleri 4. Şube Müdür Vekili olan İstihkam Albayı Nakamura Shinichiro'nun itirazıyla Yamagata Aritomo Nagoya Kalesi'nin korunmasına karar verdi.

Pasifik Savaşı sırasında USAAF'nin gerçekleştirdiği 14 Mayıs 1945 tarihli Nagoya Bombardımanında yaygın bombasının tam isabetiyle yandı.

1959 yılında Tenshu betonarme ile yeniden inşa edildi.