İlçemizin ne zaman ve kimler tarafından kurulduğu kesin olarak bilinmemektedir. M.Ö. 2000 yılları ile M.Ö. 1000 yılları arasında Anadolu’da yaşayan Etilerin sınırları, batıda Ege Denizinden doğuda Erzurum’a uzanmaktaydı. Koyulhisar o zamanlar Eti İmparatorluğu sınırları içerisinde yer alıyordu.

Etiler döneminde ilçemiz Kolonya ismini taşımakta ve bugünkü Koyulhisar ile Suşehri ilçesi arasındaki Hanlar denilen (Yemişli) mevkideydi. Bugün o dönemden kalan Hanların kuzeyinde bir kale, güney kısmında Aydınlar köyünün batısında bir höyük bulunmaktadır. Fakat bu bölgede heyelan ve toprak kayması tehlikesi bulunduğundan kazı çalışmaları yapılamamıştır.

Şehir sonradan yer değiştirerek bugünkü ilçe merkezinin 3 km kuzeyinde Akpınar denilen yerde kurulmuştur. Akpınar’da kesme taştan yapılmış saray kalıntısı, Akpınar’ın kuzeyinde Kayalar mevki ile batısında Mezarlık Deresi denilen yerlerde halen Müslümanlara ait olmayan mezarlar, Akpınar’ın doğusunda ise Müslümanlara ait mezarlar (Ağ Mezarlık) bulunmaktadır.

Anadolu; Etiler’in, Frigler’in, Kimmerler’in ve Medler’in yıkılmalarından sonra Persler’in istilasına uğramıştır. Makedonya Kralı Büyük İskender Persler’i Anadolu’dan atarak Hindistan’a kadar uzanan büyük bir imparatorluk kurmuştur. İskender’in ölümünden sonra generallerinden Selevkos, Orta, Kuzey, Güney ve Doğu Anadolu’nun tamamına hakim olmuştur. Selevkoslar’ın devleti Romalılar tarafından yıkılarak Roma’ya bağlanmıştır. M.Ö. 280 yılında Trabzon’da Pontus Krallığı kurulmuş ve Pontus Kralı’nın 8. Mitridates Dionizos Niksar, Koyulhisar ve Şebinkarahisar’ı M.Ö. 120-63 yıllarında işgal etmiştir. Ölümünden sonra Romalılar, Pontuslar’a ait bütün toprakları nüfuzları altına almışlardır.
“Müslüman Türkler’ in Anadolu’ya gelişlerine kadar Bizans’ın Anadolu’ya hakimiyeti devam etmiştir. 1071 Malazgirt Savaşı’ndan sonra Türklerin hakimiyetine geçen Koyulhisar, bir süre Danişmentliler’in egemenliğinde kaldıktan sonra Anadolu Selçuklu Devleti’nin eline geçmiştir. 1243 yılında Kösedağ Savaşı’nda Selçuklular Moğollara yenilince Selçuklulara ait topraklar Moğolların eline geçmiştir. Anadolu’da Moğol-İlhanlı hakimiyetinin sona ermesi ve Sivas ile Kayseri civarlarında Eretna Beyliği’nin kurulması ile burası Eretnalılar’ın eline geçmiştir. 1380 yılında Kadı Burhanettin, Eretna Beyliği’ni yıkarak topraklarına hakim olmuştur. Kadı Burhanettin’in 1397 yılında Akkoyunlu Emiri Karayölük Osman Bey tarafından öldürülmesi üzerine ülkesinin büyük bir kısmı halkın isteği ile Osmanlı idaresine geçmiştir. Bu kargaşa sonrasında, tarihi tam olarak bilinmemekle beraber Koyulhisar Trabzon’daki Pontus Rum Devleti’nin eline geçmiştir. Akkoyunlu hükümdarı Uzun Hasan Trabzon Rum Pontus Kralı IV. Loannes’in kızı Prenses Despina Katherina ile evlenince Koyulhisar Kalesi Rum Pontus Kralı tarafından Uzun Hasan’a çeyiz olarak verilmiştir. Sık sık saldırılar düzenleyen Fatih Sultan Mehmet’in korkusundan Uzun Hasan, şimdiki Yukarıkale Köyü’nün doğusundaki tepe üzerine bir kale yaptırmıştır. 1461 yılında Uzun Hasan’ın Koyulhisar’ı zapt etmesi üzerine Fatih Sultan Mehmet, buraya Şaraptar Hazma Bey’i göndermiş, arkasından kendisi kaleyi teslim almış ve buradan da Trabzon’a devam etmiştir. Fatih Sultan Mehmet Trabzon’u ele geçirerek deniz yoluyla İstanbul’a döndüğü sırada Uzun Hasan tekrar Koyulhisar’ı ele geçirmiştir. Fatih Sultan Mehmet Otlukbeli Savaşı’na giderken Koyulhisar’ı tekrar Osmanlı idaresine geçirmiştir. 1473 yılından sonra ilçemiz el değiştirmemiş ve işgal görmemiştir.

İlçemiz Kurtuluş Savaşı’nda işgal görmemiş olduğu halde şehitliği olan Orta Anadolu’nun ender yerleşim merkezlerinden birisidir. 1916-1917 yıllarında Rus Orduları Doğu Anadolu’dan yurdumuza girip Erzincan ile Suşehri arsındaki Çardaklı Mevkii’ne ilerledikleri zaman cephe gerisinde askeri hastane Koyulhisar’a kurulmuştur. Cepheden gelen yaralı Mehmetçiklerden şehit olanlar için ayrı ayrı mezarlar kış şartlarının ağır olmasından dolayı açılamadığından; askerler açtıkları hendeklere şehitlerimizi beşer-onar defnetmişlerdir. Şehitlerimizin ilçe topraklarında yattıkları bu mezarlık 1971-1972 yılında o zamanki Askerlik Şube Başkanı olan Binbaşı Ekmeleddin Yalçın Bey tarafından Kara Kuvvetleri Komutanlığımızdan temin ettiği ödenekle Şehitlik inşa edilmiştir. 1916-1917 yıllarında Rusların Erzincan Çardaklı Mevkii’ne kadar geldiklerinde Koyulhisar halkının tarihe geçecek bir fedakarlığı olmuştur. 98 ton yiyecek maddesini ilçemiz halkı sırtlarında Suşehri’ne 24 saat gibi kısa bir sürede taşımışlardır. Koyulhisarlıların bu fedakâr davranışına General Fehim Paşa teşekkür konuşması yapmıştır. Koyulhisarlıların yaptıkları bu büyük hizmete karşılık olarak devlet, büyük mali sıkıntıların içinde iken Türk Ordusu’nun Koyulhisar halkına şükran borcu olarak bir anıt çeşme yapılmıştır.

 İlçemizin adının kaynağı hakkında ise çeşitli söylentiler vardır. Koloneia, Kule-Hisar, Koyulu-Hisar gibi isimlerin yanı sıra batılı kaynaklardan da Kaili-Hisar, Kuili-Hisar şeklinde geçmektedir. Türkler Anadolu’ya yerleşmeden önce ise ilçemiz Trabzon Rum İmparatorluğu’na bağlı olup; ismi Kolonya idi. Selçukluların XV. asır ortasından itibaren de Osmanlı hakimiyetinde bulunan ilçemizin o zamanki adı ise Muşaz dır. 
Eğriçimen Yaylası çevresinde Etiler devrine ait bazı kalıntılar bulunarak, eserler Müzeler Müdürlüğüne intikal ettirilmiştir.