Objek wisata ini terletak di atas bukit di Kelurahan Dembe, Kecamatan Kota Barat, Kota Gorontalo. Benteng ini dibangun sekitartahun 1522.
Adapun sejarah pembangunan benteng ini adalah sebagai berikut.

Sekitar abad ke-15,dugaan orang bahwa sebagian besar daratan Gorontalo adalah air laut. Ketika itu,Kerajaan Gorontalo di bawah Pemerintahan Raja Ilato, atau Matolodulakiki bersama permaisurinya Tilangohula (1505–1585). Mereka memilik tiga keturunan, yakni Ndoba (wanita),Tiliaya (wanita),dan Naha (pria).Waktu usia remaja,Naha melanglang buana ke negeri seberang,sedangkan Ndoba dan Tiliaya tinggal di wilayah kerajaan.
Suatu ketika sebuah kapal layar Protugis singgah di Pelabuhan Gorontalo Karena kehabisan bahan makanan, pengaruh cuaca buruk, dan gangguan bajak laut.

Mereka menghadap kepada Raja Ilato. Pertemuan tersebut menghasilkan sebuah kesepakatan, bahwa untuk memperkuat pertahanan dan keamanan negeri, akan dibangun atau didirikan tiga buah benteng di atas perbukitan Kelurahan Dembe, Kecamatan Kota Barat yang sekarang ini, yakni pada tahun 1525.

Ternyata, para nakhoda Portugis hanya memperalat Pasukan Ndoba dan Tiliaya ketika akan mengusir bajak laut yang sering menggangu nelayan di pantai.Seluruh rakyat dan pasukan Ndoba dan Tiliaya yang diperkuat empat Apitalau, bangkit dan mendesak bangsa Portugis untuk segera meninggalkan daratan Gorontalo.Para nakhkoda Portugis langsung meninggalkan Pelabuhan Gorontalo.

Ndoba dan Tiliaya tampil sebagai dua tokoh wanita pejuang waktu itu langsung mempersiapkan penduduk sekitar untuk menangkis serangan musuh dan kemungkinan perang yang akan terjadi.Pasukan Ndoba dan Tiliaya,diperkuat lagi dengan angkatan laut yang dipimpin oleh para Apitalau atau ‘kapten laut’, yakni Apitalau Lakoro, Pitalau Lagona, Apitalau Lakadjo, dan Apitalau Djailani.

Sekitar tahun 1585, Naha menemukan kembali ketiga benteng tersebut. Ia memperistri seorang wanita bernama Ohihiya.Dari pasangan suami istri ini lahirlah dua putra, yakni Paha (Pahu) dan Limonu.Pada waktu itu terjadi perang melawan Hemuto atau pemimpin golongan transmigran melalui jalur utara. Naha dan Paha gugur melawan Hemuto. Limonu menuntut balas atas kematian ayah dan kakaknya. Naha, Ohihiya, Paha, dan Limonu telah memanfaatkan ketiga benteng tersebut sebagai pusat kekuatan pertahanan. Dengan latar belakang peristiwa di atas,maka ketiga benteng dimaksud telah diabadikan dengan nama sebagai berikut. Pertama, Otanaha.
Ota artinya benteng. Naha adalah orang yang menemukan benteng tersebut. Otanaha berarti benteng yang ditemukan oleh Naha.

Kedua,Otahiya. Ota artinya benteng. Hiya akronim dari kata Ohihiya, istri Naha Otahiya, berarti benteng milik Ohihiya. Ketiga Ulupahu.Ulu akronim dari kata Uwole,artinya milik dari Pahu adalah putera Naha.Ulupahu berarti benteng milik Pahu Putra Naha.

Benteng Otanaha, Otahiya, dan Ulupahu dibangun sekitar tahun1522 atas prakarsa Raja Ilato dan para nakhoda Portugis.