Tipik bir Orta çağ kalesidir. Comana Pontica'dan (Gümenek) göç eden Hıristiyan topluluğun yerleştiği bölgededir. Dış kale sur duvarları tamamen ortadan kalkmış, iç kale duvarlarının bir bölümü ayaktadır. Tokat il merkezinin kuzeybatısında, yöreye hâkim bir yükseklikte, kayalık alanda bulunan bu kalenin yapım tarihi kesin olarak bilinmemektedir. Bununla beraber, MS.V.-VI. Yüzyıllarda bu kalenin bilindiği kaynaklardan öğrenilmektedir. Bu dönemde kale Eudoksia veya Dokeia olarak tanınıyordu. Danişmentli Melik Ahmet Gazi tarafından 1074 yılında ele geçirilmiş, daha sonra Selçuklu ve Osmanlı egemenliğine girmiştir.
Osmanlı tarihçileri bu kaleden birinci derecede “müstahkem mevkii” olarak söz etmişlerdir. Timur ve Şah İsmail’in akınları sırasında da bu kale ele geçirilememiştir. Ayrıca kalenin Çardak-ı Bedevi denilen zindanında Bizans İmparatoru A.Diogenis başta olmak üzere birçok ünlü kişinin tutsak olduğu da yine kaynaklardan öğrenilmektedir. Evliya Çelebi 1656 yılında Tokat’a gelmiş ve bu kaleden söz etmiştir:
“Kale yüksek bir tepe üzerinde, kesme taş ile yapılmış olup o kadar büyük değildir. Etrafı burçlar ve kuleler ile süslenmiş olup, etrafında hendek yoktur. Korkusuz bir surdur ki Samanyolu gibi göğe baş uzatmıştır. Dört tarafı çok sarp olduğundan asla hendek olacak yeri yoktur. Bütün etrafı şahin, kartal ve zağanos yuvaları, çeşitli rengârenk kayalardır. Batıya bakan bir kapısı vardır. Kalenin içinde dizdar evi, kethüda, imam, müezzin ve kale mehterhaneleri, cephane odaları, zahire ambarları, su sarnıçları, ceylan yolu adlı suyolları vardır ki tam 362 basamak taş merdivenle nehre inilir. Batı tarafındaki ayar kayası bu kaleye havaledir. Yıldırım Han Camii var diğerlerden bir şey yok. Göğe kadar yükselmiş bir kale olmakla değme adam bir saatte çıkamadığından gece gündüz kapısı kapalıdır. Bekçileri daima bekleyip, silahla hazır dururlar. Çünkü aşağı şehir ahalisinin bütün kıymetli malları kalede muhafaza olunur. Tokat’ın bütün suçlu ve katilleri burada mahpustur ki Kudüs-ü Şerif zindanında ve Acemlerin Kahkaha Kalesine benzer.”