İlçemizin ne zaman ve kimler tarafından kurulduğu kesin olarak bilinmemektedir. M.Ö. 2000 yılları ile M.Ö. 1000 yılları arasında Anadoluda yaşayan Etilerin sınırları, batıda Ege Denizinden doğuda Erzuruma 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ı tehsi 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ınarda 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; Etilerin, Friglerin, Kimmerlerin ve Medlerin yıkılmalarından sonra Perslerin istilasına uğramıştır. Makedonya Kralı Büyük İskender Persleri Anadoludan atarak Hindistana kadar uzanan büyük bir imparatorluk kurmuştur. İskenderin ölümünden sonra generallerinden Selevkos, Orta, Kuzey, Güney ve Doğu Anadolunun tamamına hakim olmuştur. Selevkosların devleti Romalılar tarafından yıkılarak Romaya bağlanmıştır. M.Ö. 280 yılında Trabzonda 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, Pontuslara ait bütün toprakları nüfuzları altına almışlardır.
“Müslüman Türkler in Anadoluya gelişlerine kadar Bizansın Anadoluya hakimiyeti devam etmiştir. 1071 Malazgirt Savaşından sonra Türklerin hakimiyetine geçen Koyulhisar, bir süre Danişmentlilerin egemenliğinde kaldıktan sonra Anadolu Selçuklu Devletinin 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. Anadoluda Moğol-İlhanlı hakimiyetinin sona ermesi ve Sivas ile Kayseri civarlarında Eretna Beyliğinin kurulması ile burası Eretnalıların eline geçmiştir. 1380 yılında Kadı Burhanettin, Eretna Beyliğini yıkarak topraklarına hakim olmuştur. Kadı Burhanettinin 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 Trabzondaki Pontus Rum Devletinin eline geçmiştir. Akkoyunlu hükümdarı Uzun Hasan Trabzon Rum Pontus Kralı IV. Loannesin kızı Prenses Despina Katherina ile evlenince Koyulhisar Kalesi Rum Pontus Kralı tarafından Uzun Hasana çeyiz olarak verilmiştir. Sık sık saldırılar düzenleyen Fatih Sultan Mehmetin 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 Trabzona devam etmiştir. Fatih Sultan Mehmet Trabzonu ele geçirerek deniz yoluyla İstanbula 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 Anadolunun ender yerleşim merkezlerinden birisidir. 1916-1917 yıllarında Rus Orduları Doğu Anadoludan yurdumuza girip Erzincan ile Suşehri arsındaki Çardaklı Mevkiine ilerledikleri zaman cephe gerisinde askeri hastane Koyulhisara 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ı Mevkiine kadar geldiklerinde Koyulhisar halkının tarihe geçecek bir fedakarlığı olmuştur. 98 ton yiyecek maddesini ilçemiz halkı sırtlarında Suşehrine 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 Ordusunun 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 Anadoluya yerleşmeden önce ise ilçemiz Trabzon Rum İmparatorluğuna 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.
