Müşterek hükümdar Maximianus'a devletin batı yarısını bırakıp İmparatotluğun daha zengin olan doğu yarısında ve çoğunluğu Nikomedia (lzmit)'te oturan Diocletianus'un ölümünden sonra çıkan kargaşanın ardından M.S.324'de tek başına tahta çıkan ve eski Yunan kolonisi Byzanytium'un yerinde M.S.324'te bir şehir inşaatına başlayan Costantinus M.S.330'da açılışını yaptığı Byzantıum/Constantinopolis/İstanbul'u devletin başkenti yapmıştı M.S.476'da İmparatorluğun tek başkenti haline gelen bu şehir daha sonra Doğu Roma İmparatorluğu'nun, büyük Roma İmparatorluğu'nun tek varisi durumuna gelmesi ile dünyanın sayılı şehirleri arasına girmişti.

Dioecletianus'un reformlarına göre Roma İmparatorluğu dört büyük Prefelikliğe, bu Prefelikler de 12 Dioecesisliğe ayrılmıştı. Bu düzenlemede Doğu Prefelikliği'nin Pontus Dioecesisliği'ne bağlı Pontos Polemoniacus vilayeti içinde olan Trabzon, yetkileri sınırlı sivil valiler tarafıdan yönetilirken, askeri bakımdan birkaç vilayeti kapsayan Armenia Duxlüğüne bağlı idi.

5. yüzyılın başlarına ait olduğu kabul edilen Notitia Dignitatum adındaki saray hizmetlileri ile askeri ve mülki idarecilerin resmi listesi olan belge bize Trabzon'un idari durumu hakkında daha ayrıntılı bilgi verir.

Bu belgeye göre Armenia Duxluğü içindeki 7 castellondan biri olan Trabzon'da Pontik II. Legionun karargahı da bulunmaktaydı. Aynı dönemde Sürmene'de bir piyade bölüğü ve Rize'de de bir suvari bölüğünden oluşan garnizonlar vardı. Bu yüzyılda Bizans'ın doğu sınırının Rize'nin doğusuna kadar gerilediğini düşünürsek bölgenin stratejik önemini daha iyi anlamış oluruz. Trabzon, Roma imparatorları Vespasien, Neron ve Hadrien zamanında üstlendiği, doğu sınırında yapılan Seferlerde ordunun ikmalinin sağlandığı bir üs ve liman gerevini Bizans İmparatorluğu döneminde de yüklenmiştir. Justinianos I.(527-565) zamanında batıda yapılan savaşlarda başarılar elde edilmişse de doğu sınırında İran'a karşı savunma sistemi zayıflamıştı.

Bu dönemde Justinianus, Trabzon'a gerekli önemi göstermiş, surlarını restore ederek savunmasını kuvvetlendirmişti. şehrin su ihtiyacını karşılamak için su kemerleri inşa ettirmiş ve bu kemere şehrin koruyucu azizi olan St.Eugenes'ın adını vermiş, şehirdeki bir çok kiliseyi yeniden restore ettirmişti. Rize'nin kalesini de restore ettirip savunmasını güçlendiren Justinianus bölgede birbiriyle bağlantılı birçok müstahkem mevki inşa ettirerek Rize'nin doğusuna kadar geri çekilen Bizans sınırını emniyet altına almaya çalışmıştı.

Trabzon'un civarında dağlık bölgelerde yaşıyan Can/Tzan/Sanni adı verilen halk tam itaat altına alınamadığı için çevredeki Bizans yerleşimlerine ya da ikmal kollarına sık sık baskınlar düzenliyor yağma yapıyorlardı. Justinianus, Gümüşhane/Canca'dan Araklı burnuna kadar olan bölgede yaşayan Canları yenerek Bizans hakimiyeti altına almak için M.S.528 yılında yerli komutanlardan Tzitas'ı göndermiş ve onları itaat altına almıştı. Sık ormanlarla kaplı bölgede ormanları kestirerek yollar açtırmış, bu yolların emniyetini sağlamak için kuleler inşa ettirmiş ve bu halkın Hıristiyanlaşarak dindar ve itaatli insanlar olması ve imparatorluğun sınırlarında muhafızlik yapmaları için çalışmıştır.

Heraclius döneminde (610-641) Anadoluda İran istilası yayılmış, İranlılar İstanbul önlerine kadar ilerlemişlerdi. Heraklius Anadolu arazisini askeri bölgelere(Thema) ayırarak yeni bir düzenleme yapar. Kolordu manasındaki Thema kelimesinin ad olarak verildiği bu bölgelere askeri birlikler iskan edilimiş, askerlere sonradan çocuklarına bırakabileceği araziler verilmiştir.

Tarihçiler Heraclius'un 622 ile 628 arasında İranlılar üzerine üç sefer yaptığını kaydeder. 622 ve 623 yıllarındaki seferlerde ordunun ikmali için Karadere-Satalayolunu kullanan Heraclius 625 kışını Sivas üzerinden çekildiği Karadeniz bölgesinde geçirir. İran ordusunun Anadoluyu baştan başa geçerek Kadıköy'e kadar ilerlediği zaman Heraclius Trabzonun doğusunda, Karaderenin yanındaki Sürmene/Sousourinama (bugünkü Araklı)'da idi. Buradan kuşatma altındaki başkenti ile kolayca haberleşmeyi sağlarken Hazar Türklerinin liderleri ile görüşmeler yaparak Bizans-Hazar ittifakını gerçekleştirmiş ve İran'ı yenerek 628'de başkente muzaffer bir şekilde dönmüştü.

Bizans devletinin İran'a karşı kazandığı zaferlerin başlangıç yılı 622 Hz.Muhammed'in Mekkeden Medineye hicret ettiği yıl idi. İranlıların İstanbul kapılarına dayandığı sıralarda Hz.Muhammed' inen Rum Suresi'nde mağlup olan Romalıların birkaç yıl içinde kazanacaklarını ve o gün inananların ferahlanacağı bildirilmekteydi. Nitekim Romalıların yendiği ateşe tapan Sasamler peygamberin vefatından birkaç yıl sonra Müslümanların ilk hücumu ile yıkılmış, Bizans ise İran'la yaptığı savaşlarda elde ettiği doğu eyaletlerini kaybetmişti.

Hz. Ömer zamanında (634) Bizans topraklarına giren Muslümanlar 636'da Yermuk savaşında Bizans ordusu yenmişti. 646' da Bizans'ı Mısır'dan da atan Suriye valisi olan Muaviye komutasında Müslüman Araplar kuzeyde Kayseri'ye kadar olan toprakları işgal etmiş 663'de yeniden başlayan Arap akınları batıda İzmir ve İstanbul'a kadar ulaşmış ve 674 yılında İstanbul kuşatılmıştı.

7. Yüzyıl başlarında Bizans'ın İran ve Araplarla yaptığı yıpratıcı savaşlar sonucu Anadolu harab olmuş ve nüfus azalmıştı. Balkanlarda Bulgar ve Slav kitlelerine karşı zafer kazanmış olan Bizans onları Anadoluya geçirerek Araplara karşı savunmada onlardan yararlanmıştır.

Anadolu'ya yönelen Müslüman Arap akınları Trabzon bölgesinide hedef almış 705-711 yıllarında Ankara'ya kadar ilerleyen Araplar aynı dönemde Trabzon bölgesine de yönelmişlerdi. 715'te Arapları Trabzon bölgesinden atan Anatolikon Theması'nın Strategos'u Isauralı Leon daha sonra Bizans tahtını da eline geçirmiştir.

Anadolu'da Müslüman Araplarla Bizans arasında sürüp giden mücadeleye ilerdeki asırlar boyunca doğuda Müslüman olmaya başlayan Türkler İslam ordusunda, Karadeniz'i kuzeyinden Balkanlara inmiş ve burada Bizansla ilişkiye geçmiş olan Bulgar, Uz, Peçenek Macar gibi Türk kitleleri de Bizans ordusunda hizmet etmiştir.

Maveraünnehir bölgesinden gelen çok sayıda Müslüman olmuş Türk boyu uc vilayeti denilen Bizans sınırına yerleşririlmiş ve asırlar boyu süren bir mücadele döneminde Afşin, Aşnas, İnak, Boğa el-Kebir Vasıf el-Türki gibi bir çok ünlü Türk komutan sahneye çıkmıştır.

Doğuya yaptıkrı seferlerde Trabzon'u üs olarak kullanan bir başka Bizans İmparatoru Basileios II. (967-1025)'dir. Hayatının son yıllarında Gürcistan ve Vaspurağan bölgelerini Bizans'a ilhak eden Basileios 11.1021/22 kışını Trabzon'da geçirirken burada Abhazya'ya yapacağı sefer için donanma inşa ettiriyordu. Bu sırada Ermeni Ani Kralı Symbad (1018-1041) Basileios'a bir heyet yollayarak Gürcü müttefiklerinin başına gelenlerden kurtulmak için ülkesini ölümünden sonra Bizans'a bırakmak için bir anlaşma önermişti. Bu isteği kabul edilen Symbad'dan başka Vaspuragan Kralı Senek'erin ve komşusu İbn ad-Dayrani de Trabzon'a heyet göndermiş ve devletlerini para karşılığı Bizans'a satmışlardı.

Müslüman Araplarla Bizans arasında 7.yy da başlayıp 11 .yy sonuna kadar devam eden mücadeleyi Selçuklu Türklen'nin Anadolu'yu Müslümanlaştırıp Türkleştirmelerinin bir başlangıcı olarak görmek gerekir.

Malazgirt savaşı öncesi daha ziyade keşif ve yağma gayesi ile yapılan akınlarar Malazgirt'ten sonra iskan etme ve yurt açma gayesi taşıyordu. Nitekim 1071'de Malazgirt zaferinden sonra Tükmenler tüm Anadolu'a yayılmış ve zaferi takip eden ilk yıllarda Türk akıncıları Trabzon bölgesini ele geçirmişti.

Trabzon ve çevresini Türkmenlerden kurtarmak için bir ordu ile bölgeye gönderilen Bizans ordusunun komutanı olan Thedore Gavras, 1075 yılında bölgeyi Türkmenler'den geri alır. Bu başarıdan sonra İstanbul'a dönen Thedore Gavras Bizans İmparatoru Aleksius Komnenos I. (1081-1118) tarafından Trabzon ve çevresini içine alan ve merkezi Trabzon olan Haldiya Themasının valiliğine atanır.

Burada adeta bağımsız bir şekilde davranan Thedore Gavras Niksar ve Şebinkarahisar'ı Emir Danişmend Gazi kuvvetlerine karşı müdafa eder ve Trabzon'un sınırlarını Bayburt bölgesine kadar genişletir. Trabzon'u Gürcü akınlarına karşı savunur. Samsun'dan Gümüşhane'ye kadar olan bölgede iç kesimlerden sahile inen geçitleri kontrol altında tutacak kalelerden bir savunma sistemi oluşturarak Samsun'dan Trabzon'un doğusuna kadar olan sahili emniyet altına alır.

1098'de Bayburt yakılarında ve Çoruh nehri kenarında Danişmend Gazi'nin oğlu İsmail ile tutuştuğu bir savaşta öldürülen Thedore Gavras'tan sonra oğlu Gregory Gavras (Taronites) 1103'te Trabzon valiligine (Haldiya Düklüğü) atanmıştır. Babasının Trabzon valiligi esnasında İstanbul'da rehin tutulan Gregory babası tarafından 1091'de Sinop'a kaçırılmış fakat sonra iade edilmişti. Babasının gibi o da Trabzon bölgesinde bağımsız hareket ediyordu. 1106'da Emir Danişmend'le evlilik yolu ile bir ittifak kurmuş ve Şebinkarahisar kalesindeki varlığını sağlamlaştırmıştı. Bu davranışı nedeni ile muhtemelen 1107'de İstanbul'dan John Komnenos kumandasındaki bir kuvvet tarafından yakalanmış ve İstanbul'a gönderilmiş, fakat daha sonra affedilerek itibari iade edilmiştir.

1119'dan önce Trabzon valiliğine atanan Constantin Gavras da çevresindeki Türkmenler'den destek alarak bölgeyi Bizanstan yarı bağımsız bir şekilde yönetmişti. 1140 sonlarına kadar Trabzon'da hüküm sürdüğü kesin olan Costantin Gavras Trabzon Çevresindeki Türkmen emirlerinden Mengücekli İshakla ittifak yaparak 1120'de Artuklu Belek ve Danişmendli Melik Gazi kuvvetleri ile Şiran yakınlarında karşılaşır. Bu savaşta Trabzon ve Mengücekli ittifakı yenilgiye uğrayarak çok ağır bir zaiyyat verirler. Constantin Gavras'in 5000 askeri öldürülmüş kendi ve Mengücekli İshak Bey esir düşmüştü. İshak Bey Artuklu Belek'in damadı olduğu için canını kurtarırken Constantin Gavras da 30.000 Dinar karşılığı fidye ödeyerek serbest kalmıştı.

1139-1140'da Johon Komnenos II (1118-1143)'nin Canik bölgesine bir sefer düzenlediğini ve Haldiya Themasını tekrar Bizans'a bağladığını görüyoruz. Bu sefer sırasında Isaac Komneos'un oğlu olan Jhon Komnenos (çelebi) Selçuklulara katılmış ve Sultan Mesud'un kızı ile evlenmiştir. Constantin Gavras'ın ölümünün bu seferden sonraki bir tarihte olması muhtemeldir ve tekrar Bizans İmparatorluğu'nun bir parçası haline gelmiş olan Haldiya Themasına 1160'ların ortalarında Nikephoros Palaiogolos yeni dük olarak atanmıştır.

Gavras ismi kesinlikle Yunanca, Pontus Rumcası veya Lazca değildir. Haldiya Theması orijinli olduğu kabul edilen ailenin birkaç üyesinin de Selçuklu sarayının hizmetinde olduğu biliniyor. Bunlardan Ihtiyar ad-din Hasan bin Gavras, Sultan II.Kılıç Arslan'ın vezirleri arasındadır.