Setelah membangun Benteng Kastela, Portugis kemudian membangun sebuah benteng kecil di sebelah timur Kota Gam Lamo. Letak benteng itu berada di ketinggian kurang lebih 50 meter dari permukaan laut. Berbentuk segi empat dengan panjang 28 meter dan lebar 26 meter, di mana setiap sudutnya dilengkapi dengan bastion. Bagian tengahnya terdapat sebuah lubang dan ada juga tangga dan kolam di sebelah timur. Sementara dindingnya tersusun dari batu andesit, batu karang dan batu kapur.
Mulai dibangun pada tahun 1532, kemudian benteng ini dinamakan Fort San Jao. Awalnya benteng ini difungsikan untuk menjaga keamanan antara Ternate dan Tidore dan disiapkan untuk mengantisipasi serangan dari bangsa Spanyol yang mendiami kawasan Rum, pulau Tidore. Namun, pembangunan benteng ini sempat terhenti, dikarenakan Portugis kalah dalam perang melawan rakyat Ternate yang dipimpin oleh Sultan Baabullah. Dengan kekalahan itu, Portugis harus angkat kaki dari Ternate tahun 1575.
Keadaan ini langsung dimanfaatkan oleh Spanyol untuk menguasai Benteng San Jao, lalu melanjutkan kembali pembangunan benteng yang sempat terbengkalai. Tahun 1606 pembangunan benteng telah selesai, kemudian nama Benteng San Jao diubah menjadi Benteng Santo Pedro e Paulo. Perubahan nama tersebut sebagai bentuk penghormatan atas jasa Gubernur Don Pedro de Acuna. Selanjutnya, Spanyol juga melengkapi benteng tersebut dengan enam buah meriam beserta amunisinya dan menempatkan beberapa pasukan untuk menjaga dan mengawasi kondisi yang ada di sekitar benteng.
Masyarakat Ternate lebih mengenal Benteng Santo Pedro dengan sebutan Benteng Kota Janji. Dari cerita masyarakat yang beredar, mereka mempercayai bahwa di benteng itu, Sultan Baabullah pernah mengadakan pertemuan dan menyepakati perjanjian dengan pemerintahan Portugis.
