Benteng Otanaha terletak di atas bukit di Kelurahan Dembe I, Kecamatan Kota Barat, Kota Gorontalo. Benteng ini dibangun sekitar tahun 1522. Benteng Otanaha terletak di atas sebuah bukit, dan memiliki 4 buah tempat persinggahan dan 348 buah anak tangga ke puncak sampai ke lokasi benteng. Jumlah anak tangga tidak sama untuk setiap persinggahan. Dari dasar ke tempat persinggahan I terdapat 52 anak tangga, ke persinggahan II terdapat 83 anak tangga, ke persinggahan III terdapat 53 anak tangga, dan ke persinggahan IV memiliki 89 anak tangga. Sementara ke area benteng terdapat 71 anak tangga, sehingga jumlah keseluruhan anak tangga yaitu 348.

Pada sekitar abad ke 15 daratan gorontalo diduga masih sebagian besar diliputi oleh air laut. Ketika itu wilayah gorontalo sudah berbentuk kerajaan dibawah pimpinan raja ilato (matolodulakiki) bersama permaisurinya tolangohula (1505-1585). Keturunan mereka terdiri dari tiga orang anak, masing-masing, Ndoba (wanita), Tiliaya (wanita), dan Naha (pria).

Sewaktu berusia remaja, Naha pergi melanglang buana, sementara itu Ndoba dan Tiliaya tetap tinggal di wilayah kerajaan. Suatu ketika sebuah kapal layar Portugis singgah di Pelabuhan Gorontalo. Karena kehabisan bahan makanan, pengaruh cuaca buruk, dan gangguan bajak laut. Kesempatan ini dimanfaatkan oleh para nahkoda Portugis untuk bertemu dengan Raja Ilato yang merupakan penguasa Kerajaan Gorontalo.

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 para Apitalawo (kapten laut) masing-masing Apitalawo Lakoro, Apitalawo Laguna, Apitalawo Lakandjo, dan Apitalawo Djailani, bangkit dan mendesak bangsa Portugis untuk segera meninggalkan daratan Gorontalo. Para nakhkoda Portugis langsung meninggalkan Pelabuhan Gorontalo.

Pada tahun 1585, Naha kembali dari perantauan dan menemukan ketiga benteng. Ketika itu Naha memperistri seorang wanita bernama Ohihiya. Dari pasangan suami istri ini lahirlah dua orang putra yaitu Paha (Pahu), dan Limonu. Ketika terjadi perang melawan Hemuto (pimpinan rombongan transmigrasi), melalui jalur utara. Naha dan Pahu gugur melawan hemuto. Limonu menuntut balas atas kematian ayah dan kakaknya, dan berhasil membunuh dalam sebuah peperangan.Selama dalam peperangan, naha, ohihiya, pahu, dan limonu telah memanfaatkan ketiga benteng tersebut sebagai pusat kekuatan pertahanan sehingga dengan latar belakang ini, ketiga benteng ini diabadikan sebagai berikut.

1. Otanaha: Ota  berarti benteng, dan Naha berarti orang yang menemukan benteng tersebut. Jadi Otanaha berarti benteng yang ditemukan oleh Naha.
2. Ulupahu: Ulu akronim dari kata Uwole (milik dari Pahu), dan Pahu, Pahu adalah putera Naha. Jadi Ulupahu berarti benteng milik Pahu (Paha) Putra Naha.
3. Otahiya: Ota berarti benteng, dan Hiya akronim dari Ohihiya (isteri Naha). Jadi Otahihiya yaitu benteng milik Ohihiya