Pada mulanya kedatangan bangsa Portugis ke Ternate disambut dengan penuh kehangatan oleh pihak Kesultanan, dikarenakan adanya keinginan untuk menjalin kerjasama dalam perdagangan rempah. Tahun berlalu, perdagangan di antara keduanya berjalan dengan lancar. Pihak Portugis kemudian mengutarakan niatnya dan meminta izin kepada sultan untuk membangun sebuah benteng. Di mana benteng tersebut akan digunakan sebagai pos dagang sekaligus menjadi daerah untuk tempat tinggal mereka. Niat tersebut mendapat restu dari sultan, tahun 1522 pembangunan benteng dimulai. Adalah Antonio de Brito yang merupakan seorang Gubernur Koloni Portugis di Ternate yang mempelopori pembangunan tersebut. Proyek pembangunan itu kemudian dilanjutkan oleh penggantinya, Garcia Henriquez, pada tahun 1525. Benteng ini akhirnya selesai dibangun tahun 1540, di masa kepemimpinan Jorge de Castro. Selanjutnya benteng ini dinamakan Benteng Gam Lamo atau Benteng Kastela. Nama Gam Lamo itu sendiri mempunyai dua makna, desa yang sangat besar atau kota yang besar.
Dalam perjalanan sejarahnya, Benteng Kastela beberapa kali menjadi saksi bisu dari peristiwa penting yang melibatkan Kesultanan Ternate dengan bangsa Portugis. Salah satunya adalah, perjuangan rakyat Ternate yang dipimpin oleh Sultan Baabullah dalam melawan dan mengusir bangsa Portugis. Setelah pertempuran yang berlangsung selama kurang lebih lima tahun, akhirnya Portugis berhasil diusir dari Ternate pada tahun 1575. Benteng Kastela kemudian diduduki dan dikuasai oleh Kesultanan Ternate.
Nostra Senhora Del Rosario atau Gadis cantik yang sedang menggunakan kalung dari bunga mawar merupakan nama lain dari Benteng Kastela. Ada juga sumber yang menyebutkan arti dari kalimat tersebut adalah “Santa Perawan Maria Ratu Rosario”. Nama yang begitu indah, sayang yang tersisa dari keindahan tersebut hanya puing-puingnya saja. Cerita tentang kemegahan mengenai benteng terbesar yang pernah dibangun oleh Portugis di Indonesia, bahkan disebut terbesar se-Asia Tenggara, yang di dalamnya terdapat rumah pejabat, kantor dagang, gereja dan menara telah rubuh dan hilang. Sisanya, tinggal beberapa struktur tembok yang masih bisa dilihat saat ini.
