Eski bir Bizans kilisesinden camiye çevrilmiştir. Kilisenin 7. yy.’da Bizans İmparatoru Phocas’ın kızı Helena tarafından yaptırıldığı sanılmaktadır. Danişmendliler Döneminde Amasya valiliği yapan Fetih Gazi bu büyük kiliseyi camiye çevirtmiş ve ismini Fethiye Camii olarak koymuştur. Bu cami zaman içinde oldukça hasar görmüştür. 1956’da onarılarak tekrar ibadete açılan cami son olarak 2006 yılında Vakıflar Genel Müdürlüğü’nce restore edilmiştir. İlk halinde minaresi bulunmayan camiye 1883 yılında İncezade Hacı Mehmet tarafından bir minare eklenir. Kilise halinden pek az bir kısmı ayakta kalmış olan caminin duvarları tamamen sıvanıp üzeri beyaza boyandığından yapının orijinal duvar kalıntılarının tespiti mümkün olmamıştır. Cami, kilisenin apsis kısmında kuruludur. Bu nedenle caminin doğu cephesi yarım bir altıgen oluşturacak biçimde köşelidir. Kuzey duvarındaki küçük bir girişten girilen caminin batı cephesi sonradan geniş kemerli bir niş biçiminde kapatılmış, bu bölüme alt ve üst pencereler açılmıştır.