The castle was constructed in 1594 by Kuki Yoshitaka, who commanded a force of Japanese pirates, who dominated the Ise Bay area in the Sengoku period.

Kuki Yoshitaka was enlisted into the service of Oda Nobunaga in 1575 to assist him in crushing the Ikkō-ikki movement based at Nagashima.

The Kuki and Murakami navies fought in several engagements in Osaka Bay, eventually emerging victorious through their use of armored ships.

During Ieyasu's expedition against the Uesugi clan in Aizu, Kuki Yoshitaka seized the castle from his son with Toyotomi assistance.

The Kuki clan continued to rule Toba until 1633, but by this time the shogunate no longer required a naval force, and they were replaced by a succession of fudai daimyō.