Günümüze kadar ulaşabilmiş ve şimdilerde "Altınordu Kaymakamlığı" olarak kullanılmaya başlanan bina ve yanındaki diğer iki binanın inşa tarihi 1893 yılıdır. Bu binaların inşa edildiği yerde 1864 yılında Ordu kaymakamı Ethem Ağa tarafından inşa edilmiş bir hükümet konağı bulunmaktaydı. Ethem Ağa bu binayı izinsiz inşa ettirmekten dolayı soruşturma geçirmişti. Ancak inşaat durdurulmamış ve tamamlanmıştı.

Bu konuda Osmanlı Arşivi'nde bulunan 3 Ağustos 1864 tarihli belgenin sadeleştirilmiş özeti şöyledir:

"Bucak kasabası hükümet konağının eski kaymakam Edhem Ağa tarafından izinsiz olarak yaptırıldığı ve gönderdiği lâyihada bildirilen şeylerden dolayı Trabzon'a geldiğinde tahkikat yapılması için tevkif edilmesi ve konağın eksik kısımlarının tamamlanması ayrıca hapishaneye pencere açılarak içinin sıvanması hususunda dikkatli davranılarak masrafının mal sandığından karşılanması ve müfredât defterinin gönderilmesi için Sadaret'ten Rıza Efendi'ye yazı gönderildiği." (MVL. 680/20, 1281.S.29 [3 Ağustos 1864])

Kaymakam Ethem Ağa'nın yaptırdığı bu binanın ömrü uzun sürmemişti. Belgelerden anlaşıldığı kadarıyla 1887 yılı Aralık ayında bina tamamen yanmıştı. Bu yangında binada bulunan resmi evrakların da yandığı görülmektedir. Bu konudaki 1887 tarihli belgenin özeti de şu şekildedir:

"Trabzon vilâyetinden Dâhiliye Nezâretine gönderilen telgrafta, Kânûn-i evvelin (Aralık) Cuma gecesi saat sekiz sıralarında yanan Ordu kazası hükümet dairesinde dört bin kuruş ile resmi evrakın da yandığı, bu sebeple yangının çıkış nedeninin araştırıldığı ve zanlıların sorgusuna başlandığının bildirildiği." (Y.A.HUS. 209/21, 1305.R.9 [25 Aralık 1887])

Yangından sonra hükümet konağı olarak şimdiki Valilik binasının olduğu yerde bulunan Ali Paşa konağı kiralanmıştı. Yanan hükümet konağının yerinde -Altınordu Kaymakamlığı'nın bulunduğu yer- 1890 yılında yeni bir bina inşaatına başlanmıştı.