Dalam rangka memperluas pengaruh dan kekuasaan bangsa Portugis di Pulau Ternate, Antonio Pigaveta menggagas pembangunan sebuah benteng pada tahun 1540. Benteng tersebut kemudian dikenal dengan nama Benteng Santa Lucia. Singkatnya, perluasan kekuasaan dan monopoli perdagangan yang dilakukan oleh Portugis mengalami benturan dengan upaya Sultan Baabullah dalam melakukan penyebaran agama Islam. Perang tidak dapat dihindarkan dan puncaknya pada tahun 1575, Portugis berhasil diusir dari Pulau Ternate. Kondisi tersebut kemudian dimanfaatkan oleh Spanyol, Benteng Santa Lucia dikuasai dan dijadikan sebagai pos perdagangan dan pos pertahanan.
Kedatangan bangsa Belanda di Ternate menjadi ancaman yang sangat serius bagi Spanyol. Pertikaian kedua bangsa itu berujung pada peperangan dalam upaya memonopoli perdagangan rempah. Benteng Santa Lucia menjadi saksi bisu dalam peperangan yang melibatkan kedua bangsa kulit putih ini, di mana benteng tersebut digunakan oleh Spanyol sebagai pusat melancarkan serangan terhadap bangsa Belanda. Kedua negara itu silih berganti menduduki benteng yang letaknya di pesisir laut Selat Maitara. Spanyol berhasil menguasainya hingga tahun 1663. Tanggal 29 April 1798, Benteng Santa Lucia berhasil direbut oleh pasukan Kaicil Nuku (Sultan Tidore ke-19) yang dibantu oleh armada Inggris. Namun karena dikhianati, benteng tersebut dikuasai oleh Inggris pada tahun 1801. Setelah itu, Belanda berhasil merebutnya kembali dan menguasainya hingga tahun 1810.
Benteng Santa Lucia atau yang dikenal dengan nama Benteng Kayu Merah kemudian berganti nama menjadi Benteng Kalamata. Belanda mengambil nama itu dari nama seorang pangeran Ternate, Kaicil Kalamata, yang merupakan kakak dari Sultan Mandarsjah dan paman dari Sultan Kaicil Sibori Amsterdam. Dari segi arsitektur, benteng ini berbentuk segi empat yang tidak beraturan (triangulasi) dengan empat bastion yang memiliki ceruk bidik (embrasure) di parapet masing-masing bastion. Jika dilihat dari atas, benteng ini menyerupai seekor penyu. Ketebalan dindingnya lebih kurang 60 centimeter dan mempunyai ketinggian sekitar 3 meter. Dindingnya tersusun dari batu andesit dan batu karang yang direkatkan dengan memakai kalero, sejenis kapur yang dihasilkan dari pembakaran batu karang. Kapur tersebut kemudian dicampur dengan pasir dan air rendaman kulit Pohon Lubiri.
