Tokat Kalesi'nin kuruluş tarihine ve ilk kullanım dönemlerine ilişkin elde kesin bilgiler bulunmamaktadır. Fakat konumundan, plan özelliklerinden, yapım tekniği ve adının geçtiği kimi tarihsel olaylardan yola çıkılarak, yapının MS 5. ya da 6. yüzyıllarda yapılmış olduğu sonucuna varılmaktadır. Bu bulgulara ve çıkarımlara kalenin Evdoksia, Endoksia, Dokia gibi adlarla anılması eşlik etmektedir.

Surların üzerinde yükseldiği sarp kayalık aslında doğal bir kaledir. Bugün kim olduklarını bilmediğimiz ilk yerleşimcilerini ve Komana Pontika'dan (Gümenek) göçen kimi Hıristiyan grupları buraya yerleşmek için çeken de bu özellik olmalı.

Komana'nın 9 km batısındaki bu sarp kayalık, bir yandan Sivas yönündeki dar Kızıliniş Geçidini kontrol ettiği, öte yandan da dik Gıjgıj Tepe sayesinde kaleye ulaşan yolu kolayca denetleme olanağı verdiği için oldukça güvenli bir noktadır. Buna, kayalığın doğal yıkımlara dayanıklı görünümünü de eklemek gerek.

Kalenin günümüze ulaşan mimarisi birçok bakımdan Ortaçağ izlerini taşımaktadır. Kesme ve moloz taş kullanılan sur duvarları dış ve iç surlar olmak üzere kademeli biçimde doğu ve batı yönlerindeki kaya kütlelerinin üzerine oturmuştur. Kalenin planı, kuzey yönündeki doğal kayanın kapı olarak kullanılmasına olanak verecek biçimde oluşturulmuştur. Beşgen planlı yapı on sekiz burçla güçlendirilmiş ve batıda 'Ceylan Yolu' da denilen 362 basamaklı sarnıç kuşatmalar esnasında ortaya çıkan su ihtiyacını karşılamak üzere yapılmıştır. Kuleleri, burçları, mazgalları ve sur duvarlarının bir bölümü günümüze ulaşabilmiştir. İçinde çok sayıda mekân bulunmaktadır. Tonozlu yapılar ve bugün de görülebilirken, diğer mekânların sadece temelleri izlenebilmektedir. Kuzey ve güney yönündeki duvarları depremlerden ve onarım eksikliğinden ötürü büyük ölçüde yıkılmıştır. Bu yönde sadece bir burç ve ana kaya üzerindeki surlar ayaktadır.

Yalnızca uzaktan bakınca değil, içten gördükten sonra da şunu söyleyebiliriz: yapının günümüze ulaşan kesimleri bile, onun yüzyıllar boyunca uğradığı ihmale ve tahribata karşın görkemini anlatmaya yeter.

Yazılı tarih, kalenin kuruluşundan sonra uzun yıllar Bizanslıların elinde kaldığını gösterir. Selçuklu ve Osmanlı devirlerinde savunma amacıyla onarılıp yenilenen kale, bir de dönem dönem kimi isyancılara ve yöneticilere hapishane ve sığınak olmasıyla ünlenmiştir. Kaleye en son hükmeden Osmanlılar da sanırız bu özelliğini vurgulamak için, 'Çardak-ı Bedevi' demiş kaleye. 1277 yılında Memluk sultanı Baybars'ın Kayseri'ye ilerlemesinden sonra, Muineddin Pervane'nin II. Gıyaseddin Keyhüsrev'i kaçırmasını Ebu'l Fereç, 'Sultanı alarak Doqia Kalesi'ne kaçtı.' diye yazmaktadır. Bu sözler, kentin adının o günkü söylenişlerinden birini verdiği için de önemlidir.