The story begins in November 1511, when Portuguese traders in Malacca first learned the precise location of the fabled Spice Islands. An expedition under Antonio de Abreu set out, with Francisco Serrao sailing to Ternate as deputy commander. The Ternatan sultan welcomed the Portuguese, largely because he needed help against his rival, the Sultan of Tidore, who was allied with Spain. In June 1522 the Portuguese built their first fort on Ternate, Sao Joao Baptista, near the sultan's residence at Gamalama. But the promise of alliance masked an intent to monopolize. A treaty obliging the Ternatese to sell spices cheaply to the Portuguese bred resentment that simmered for decades. In 1533, a revolt led by Dajalo failed. Antonio Galvao restored order. The peace held until 1570, when Governor Lopez de Mesquita ordered Sultan Hairun murdered, and Hairun's son Babullah launched a seven-year war that drove the Portuguese from Ternate entirely by 1575.

Fort Tolukko itself was built not by the Portuguese but by the Spanish. In 1611, Governor Juan de Silva of the Philippines led an expedition to Ternate with the goal of expelling the Dutch, who had established Fort Oranje on the island in 1607. Captain Fernando de Ayala was dispatched to build a fort above the town of Tolukko, north of the Dutch position, from which the Spanish hoped to launch an assault on Fort Oranje. They named it San Juan de Toluco. The assault never came. Instead, the Spanish diverted their campaign to Halmahera's east coast, leaving Fort Tolukko strategically stranded with the Dutch fortress sitting squarely between it and the main Spanish base at Kastella to the south. By 1612, the Spanish abandoned the position. The Dutch captured it the same year and renamed it Fort Hollandia.

Jan Pieter Both, the first Governor-General of the Dutch East Indies, repaired and improved the captured fort for the VOC. But in an arrangement that reflected the political complexities of colonial Ternate, the Dutch eventually handed Fort Tolukko to the sultan so he could establish his residence there. In 1661, Sultan Mandar Syah occupied the fort with his soldiers. At some point it acquired the name it carries today, honoring Kaicil Tolukko, the tenth ruler of the Ternate Sultanate, who reigned beginning in 1692. The fort served as a site of Ternatan authority even as the balance of real power shifted steadily toward the Dutch. In 1799, Tidorese soldiers under Sultan Nuku briefly attacked Tolukko, but the combined Ternatan and Dutch forces repelled them quickly.

The continuous wars between Ternate and Tidore devastated the region. Many residents of Ternate City died of starvation or were killed in the fighting; others fled to Halmahera. The British occupied Fort Tolukko during their 1810 invasion of the Moluccas as part of the Napoleonic Wars. By 1864, the fort's buildings had deteriorated so badly that Dutch resident P. Van der Crab ordered them demolished and the site abandoned. Over a century later, in 1996, the fort was renovated as a heritage site. But the restoration came at a cost: the lack of a proper conservation process destroyed some of the fort's most distinctive features, including the tunnels that once connected the hilltop fortress to the landing point on the beach below. What remains is a six-meter stone shell on a cape, smaller and plainer than Fort Oranje down the coast, but carrying the weight of five flags and three centuries of conflict.