Komaki-jo followed Nagoya-jo (*) and Kiyosu-jo becoming Oda Nobunaga's third castle. After Nobunaga secured Mikawa province (eastern Aichi prefecture) by an alliance with Tokugawa Ieyasu, he set his sights on invading the Mino province (Gifu prefecture). To that end he built Komaki-jo in 1563.

It is said that when Nobunaga decided to build Komaki-jo he sensed that his vassals would object to moving so far from their present home of Kiyosu-jo. So that his people couldn't object, he first suggested that they build a castle on top of Ninomiya mountain in Inuyama. Ninomiya mountain is very steep and it would be a difficult place to build a castle. As soon as they objected the Ninomiya plan Nobunaga suggested Mt. Komaki instead. Having just turned down their lord's first plan, they couldn't object to his second idea too so they moved to Komaki without complaint. Nobunaga stayed in Komaki-jo until he defeated Saito Tatsuoki in 1567 and conquered Mino privince. Nobunaga then moved into Gifu-jo.

* This Nagoya-jo is different from what is known as Nagoya-jo today. The name may sound the same but the Japanese characters are different from those of the current Nagoya-jo.