Pada awalnya Benteng dikenal dengan nama Tolukko, lalu kemudian lebih dikenal dengan nama Benteng Hollandia ini, yang didirikan pada tahun 1540 oleh Francisco Serao, seorang panglima Portugis. Menurut kabar nama Tolukko merupakan nama dari pengusa kesepuluh yang duduk di singgasana Ternate yaitu Kaicil Tolukko, tetapi pada tahun 1692 sultan ini baru memerintah jadi nama benteng ini tidak mungkin diberikan untuk mengikuti nama Sultan tersebut. Benteng tersebut diperbaiki oleh Pieter Both, seorang Belanda pada tahun 1610. Dan digunakan untuk pertahanan terhadap bangsa Spanyol yang sedang menggempur pulau Ternate.
Benteng ini dipakai sebagai tempat untuk melarikan diri dari serangan Spanyol supaya mau kembali tinggal di tempat ini. Sebagian besar rakyat melarikan diri ke Benteng Malayo. Menurut laporan ada 15 hingga 20 tentara di dalam benteng ini, lengkap dengan sejumlah persenjataan dan amunisi. Pada tahun 1627 di bawah pemerintahan Gubernur Jacques le Febre, mengatakan bahwa benteng letak tidak jauh di atas bukit di sebelah Utara Benteng Malayo ini, dan dilengkapi dengan dua menara kecil.
Pada waktu itu dipimpin oleh seorang Korporal yang didatangkan dari Benteng Malayo dan menjadi sumber pemasokan bahan pangan untuk 22 orang tentara yang bertugas di dalam Benteng Tolukko. Dewan Pemerintahan Belanda mengijinkan Sultan Mandarsyah dari Ternate Pada tahun 1661, bersama pasukannya untuk tinggal di dalam benteng ini. Dengan hadirnya Sultan, maka garnizun Belanda yang ada di dalam Benteng Tolukko dikurangi sampai 160 orang. Pasukan Kaicil Nuku (Sultan Tidore yang ke-19) menyerang benteng Tolukko pada tanggal 16 April 1799, namun mereka berhasil untuk mundur oleh pasukan gabungan Ternate-VOC. Penduduk kota Ternate pada bulan Juni 1797 kini berjumlah 3.307 jiwa, akibat pertempuran dan khususnya pengepungan yang berkepanjangan oleh pasukan Nuku. Kemudian tinggal 2.157 jiwa.
Yang lain meninggal karena peperangan dan kelaparan atau melarikan diri ke Halmahera. Pada tahun 1864 di bawah pimpinan Residen P. Van der Crab, karena hampir seluruh bangunan sudah rusak maka benteng ini dikosongkan. Pada tahun 1996, dibangun kembali, namun upaya yang dilakukan malah menghilangkan keaslian bangunan seperti dihilangkannya terowongan bawah tanah yang berhubungan langsung dengan laut.
