Benteng yang mula-mula dikenal dengan nama Tolukko dan kemudian lebih dikenal dengan nama Benteng Hollandia ini, dibangun pada tahun 1540 oleh Francisco Serao, seorang panglima Portugis.
Ada yang mengatakan bahwa nama Tolukko adalah nama dari penguasa kesepuluh yang duduk di singgasana Ternate: Kaicil Tolukko; namun karena Sultan ini baru memerintah di tahun 1692 maka tidak mungkin nama benteng ini diberikan mengikuti nama Sultan tersebut. Menurut catatan sejarah Belanda, di tahun 1610 benteng Portugis tersebut diperbaiki oleh Pieter Both, seorang Belanda, dan dimaksudkan sebagai pertahanan terhadap bangsa Spanyol yang memang sedang sibuk menggempur pulau Ternate.
.
Benteng ini juga dijadikan sebagai tempat untuk menggiring rakyat yang melarikan diri dari serangan Spanyol agar mau kembali tinggal di tempat ini. Saat itu sebagian besar rakyat melarikan diri ke Benteng Malayo. Pada tahun 1612, dilaporkan terdapat 15 hingga 20 tentara di dalam benteng ini, yang dilengkapi dengan sejumlah persenjataan dan amunisi. Di bawah pemerintahan Gubernur Jacques le Febre pada tahun 1627, disebutkan bahwa benteng yang terletak tidak jauh di atas bukit di sebelah Utara Benteng Malayo ini, dilengkapi dengan dua menara kecil.
Ketika itu benteng tersebut dipimpin oleh seorang Korporal yang didatangkan dari Benteng Malayo yang juga menjadi sumber pemasokan bahan pangan untuk 22 orang tentara yang bertugas di dalam Benteng Tolukko. Pada tahun 1661, Dewan Pemerintahan Belanda mengijinkan Sultan Mandarsyah dari Ternate untuk tinggal di dalam benteng ini bersama pasukannya. Menyusul kehadiran Sultan, maka garnizun Belanda di dalam Benteng Tolukko dikurangi hingga hanya 160 orang. Pada tanggal 16 April 1799, pasukan Kaicil Nuku (Sultan Tidore yang ke-19) menyerang benteng Tolukko tetapi mereka berhasil dipukul mundur oleh pasukan gabungan Ternate-VOC. Namun akibat pertempuran dan khususnya pengepungan yang berkepanjangan oleh pasukan Nuku, penduduk kota Ternate yang di bulan Juni 1797 berjumlah 3.307 jiwa, kemudian tinggal 2.157 jiwa.
Yang lainnya meninggal akibat peperangan dan kelaparan atau melarikan diri ke Halmahera. Di bawah pimpinan Residen P. Van der Crab pada tahun 1864, benteng ini dikosongkan karena hampir seluruh bangunan sudah rusak. 1996. Dipugar kembali, tetapi upaya tersebut justru menghilangkan keaslian bangunan seperti dihilangkannya terowongan bawah tanah yang berhubungan langsung dengan laut [bentengindonesia.org]