Sasani – Bizans mücadelesi bütün hızıyla devam ederken, İslâm peygamberi Hz.Muhammed dünyaya geldi. O’nun dünyaya gelişi ile doğu ve batı dünyasında bazı mucizeler olduğu rivayet edilir. Doğu hıristiyanlığının en önemli merkezi olan Theodosiopolis’de de bir hadise olmuştur. Âşık Çelebi, eski Arap kaynaklarına dayanarak, “Erzen er-Rum’da, gayet azamet üzere bir kilise vardır. Ol-kadar büyüktür ki, ol vilayetlerde ol kiliseden âli bina ve imaret yoktur. Bu kilisenin bir kubbesi vardır ki, her taraftan 50 zira’dır. Kubbenin bazı tâkı (kemer) Hazret-i Fahr-i Âlem Resulullah Aleyh-i Vesellemin doğduğu gece, sakıt olup, ol kadar ki, ol sakıt ve mündehim olanını iâde ve mevkiine koymak istemediler. Kabil-i tamir ve termim olmayub, düşdi.”diye yazmaktadır.
Sasaniler, 642 yılında Nihavend savaşında Hz.Ömer’in ordusuna mağlup olmuş ve bu yenilgiden sonra tarihe karışmıştır. Bu yenilgiden sonra Theodosiopolis (Erzurum) yüzyıllardan beri devam eden Sasani tehlikesinden kurtuldu. Devletlerarasındaki askeri rekabet, bu defa inanç alanında şekillendi. Arabistandan hızla kuzeye doğru yayılan İslâmiyet, kısa zamanda Bizansı tehdit etmeye başladı.
Kamûs’ul A’lam’da Hz. Ömer’in halifeliği zamanında Şam’ın fethi ile görevlendirilen Cerrah oğlu Ebû Ubeyde’nin yanındaki komutanlardan Ğanın oğlu İyaz tarafından Erzurum ve dolaylarının barışçıl bir yolla fethedilerek İslâm beldeleri arasına girdiği belirtilmekte, detaylı bilgi verilmemektedir.
Halife Hz.Osman b.Affan (65l), Şam ve El-Cezire valisi olan Mu’aviye’ye bir mektup yazarak, Bizansın doğu bölgesinin fethi için Mesleme el-Fihri oğlu Habib’i (Kureyş kabilesinin Beni Fihr koluna mensuptur) görevlendirmesini emretti. Habib, Suriye seferine katılmış, Mu’aviye’nin valiliği ve daha sonra halifeliği esnasında, Anadolu gâzâsını yapmış olduğundan, kendisine Hâbibü’r-Rumi unvanı verilmiştir. Erzurum, ilk ezan sesine onun vasıtası ile kavuşmuştur.
Habib, Suriye ve el-Cezire halkından topladığı askerlerle Kalikala (Erzurum) ya geldi. Bizanslı kumandan Marianos yönetimindeki birlikler, Müslümanlarla ovada yaptıkları savaşta mağlup olup kaleye sığınmışlardır. Habib ordusunu şehrin etrafında mevzilendirdi. Şehir sakinleri yaşanan çatışmalardan sonra Müslümanlara karşı koymanın imkânsız olduğunu anlayınca, teslim olmak istediler. Habib’de Kalikala’da eski dinleri üzere kalmak isteyenlerin vergi vermek zorunda olduklarını, cizye vermek istemeyenlerin Bizans’a gidebileceklerini belirterek onları bağışladı.
Habib fetih işlemlerini tamamlayıp, vergi işlemlerini düzene bağladıktan sonra, Kalikala’da (Erzurum) birkaç ay daha kaldı. Habib b. Mesleme Ermeniyye Valisi iken H.42/M.662’de vefat etmiştir. Halk rivayetlerine göre kendi asrında Habib b.Mesleme ismi ile değil de Ebu Abdurrahman diye anıldığı, Hz. Peygamberimizin sahabelerinden olduğu ifade edilen “Abdurrahman Gazi” nin bu zat olduğu söylenmektedir.
686 yılında Müslümanlar arasında iç savaş baş gösterdi. Bizans imparatoru II. Justinianos bu durumdan faydalanarak Generali Leontius’u doğuya gönderdi. Leontius Kâlikale’yi (Erzurum) Müslümanların elinden aldı. Hıristiyan taassubunun verdiği merhametsizliğin sonucu, şehirdeki bütün Müslümanlar öldürüldü.
Emevi halifesi Abdul el-Melik (685-705) oğlu Abdullah’ı (veya Ubeydullah) 700 yılında eski sınırları muhafaza ve genişletmek için Doğu Anadolu’ya gönderdi ve ayni yıl Kâlikala (Erzurum) tekrar geri alındı. Kısa zamanda Fırat’ın yukarı havzası fethedilerek İslâm hâkimiyetine girdi. Kâlikale şehri, Müslümanların elinde olduğu sürede, yerli halk düşman saldırısından korundu. Bu durum H.133/ M.751 yılında Abbasi Halifesi Ebu Cafer el Mansur’un kardeşi Ebû’l-Abbas valiliği zamanında Bizans İmparatoru Konstantinos’in bölgeye saldırmaya başlayana kadar devam etti.
Kostantinos, önce Malatya’yı kuşattı. Malatya’yı Müslümanlardan aldıktan sonra mahiyetinde bulunan Armenialı Keysan’ı Kâlikala üzerine gönderdi. Kâlikala (Erzurum) valisi Ebu Kerime hiristiyanların yaklaştığını haber alınca, savunma yapmaya karar verdi. Şehirde yaşayan iki ermeni kardeş, ihanet edip surlarda bir gedik açarak dışarı çıkmış, Keysan’a giderek, ona kalenin giriş yolunu göstermiştir. Bizans askerlerini şehrin içinde gören Müslümanların son karşı koyması neticesiz kalmıştır. Keysan, Kâlikale’yi yaktırmış ve yıktırmış, çok sayıda esir almıştır.
İslam kaynaklarına göre Halife Ebû Cafer el-Mansur, H.139/M.756 yılında Kâlikale’de esir düşen Müslümanları, Bizanslılara kurtuluş bedeli ödeyerek hürriyetlerine kavuşturmuştur. Ayni zamanda el-Cezire ordusundan bir miktar askeri Kâlikale’ye yerleştirmiş, kaleyi de yeniden tamir ettirmiştir. Kâlikale’nin yine Müslümanlara bırakıldığı anlaşılmaktadır.
Ebû Cafer el-Mansur zamanında Kahtabe oğlu Hasan’ın Armenia valiliği esnasında (770-772) Ermeniler büyük bir isyan çıkararak Kalikala’yı kuşatma altına aldılar. Ermenilerin bu isyanını bastıramayan vali, halifeden yardım istemiştir. Halife de, İsmail el-Harisi’nin oğlu Amr kumandasında mühim bir kuvveti göndermiştir. Amr’ın Erçiş önlerinde Ermeni asilerini mağlup etmesi üzerine, bu mağlubiyeti duyan Ermeniler Kalıkala kuşatmasını bırakıp çekilmişlerdir.
Halife Muhammed el- Mehdi zamanında tekrar vali olan Useyd oğlu Yezid (H.162/M.799) yılında Kalikala boğazından(Tortum istikametinde) Bizans topraklarına sefere çıkarak üç kale zapt etmiş ve pek çok esir almıştır.
H.223/M.838 yılında Bizans İmparatoru Thepilius, Kalikala’yı kuşatmış, şehrin surlarını tahrip etmiş, ancak şehri alamayarak çekilip gitmiştir. Bunun üzerine Halife el- Mutasım Kalikala surlarını tamir ve tahkim ettirmiştir.
840 yılının Haziran ayında Kalikala (Erzurum) büyük bir depremin tahribatına maruz kaldı ve harap oldu. Büyük binalarda ve surlarda çatlaklıklar meydana geldi.
906 yılında Bizans İmparatoru VI: Leon’un doğu orduları komutanı Katakalon ile Armenia reislerinden Lalakon, Kalikala ve çevresini yağmalamış ve tahribatta bulunmuştur.
VII. Konstantinos’un komutanı Yuannes Kurkuas 922/923 yılında Kalikala’yı muhasara etti. Nasr el- Hacib’in oğlu Muhammed, Musul’dan hareketle şehrin yardımına koştu. İslam tarihçileri bu seferin akibeti hakkında bir şey söylemezler. Bizans kaynakları 934 tarihinde Kalikala/ Theodosiopolis’in yedi aylık muhasaradan sonra işgal edildiğini yazmaktadır.
H.337/M.948 yılında, Hamdanî Sayfü’d-Devle zamanında, Neca el-Haski komutasındaki İslam ordusu, Bizans idaresindeki Kalikala’yı tekrar İslam topraklarına katmıştır. Tarihçi Antakyalı Yahya, Abbasi hâkimiyetinin Kâlikala’da uzun sürmediğini, 949 yılının Eylül ayında tekrar Bizanslılara geçtiğini söylemektedir. Kâlıkala/Theodosiopolis, Bizanslılarla Müslümanlar arasında el değiştirmeye devam etmiş, bu değişikliklerde binlerce insan öldürülürken, binlercesi de yerlerinden edilmiştir. Müslümanların elinden çıkan ve tekrar Theodosiopolis ismini alan şehir Bizans İmparatorluğunun askeri merkezi olmuş, doğudan gelecek akınlara karşı, yeniden tahkim edilmiştir. Karasu yanındaki Artze/Arze (Erzen) şehri ise müstahkem olmayıp kalabalık bir ticaret merkezi idi. XI. asır Ermeni tarihçilerinden Aristakes ile Urfalı Matheos bu şehrin servet ve ihtişamından bahsederek, kalabalık bir nüfusa sahip olduğunu yazmaktadırlar.
1016 yılında Gürcistan ve Abhaz kralı I. Giorgi, Bizanslılara hücum ederek Taik ve Ouhtik (Oltu) da mağlup etmiştir. Gürcü ve Ermenilerin ayaklanmalarını bastırmak için Bizans İmparatoru II. Basileios, 1018- 1019 da doğu seferine çıktı ve Theodosiopolis’i yeniden tahkim ettirerek, askeri üs haline getirdi. Oltu vadisine hâkim vaziyetteki Namruvan/Narman ele geçirildi. Tortum-Oltu ve Kars hareketini tamamlayan Basileios Trabzon’a döndü. 1022 de, Gürcü Kralı Giorgi, Bizansla münasebetlerini bozmuş, bazı toprakları kendisine ilhak etmişdi. Bu tutum ve davranışa hiddetlenen II. Basileios, tekrar ikinci Gürcistan seferine çıktı. Oltu ve çevresini alarak sükûneti sağladı. Theodosiopolis ve çevresi kısa bir müddet hadiselerden uzak hayat sürdü. Bizans İmparatorları IV. Mikhail (1034-1041), IX. Konstantinos Monomakhos (1042-1057) devrinde bölgeyi Bizans Valileri idare etmiştir.
Hz.Osman ile başlayan ve X. Yüz yılsonlarına kadar devam eden Müslüman hâkimiyeti “Kâlikâla”, “Kâbe Mescidi”, “Abdurrahman Gazi” gibi kültürel mirası zamanımıza hediye etmiştir. Kalikala (Erzurum) , o dönemde de önemli bir kültür merkezi idi. Kadı Ebu’l- Asba İtaf b.Süfyan gibi hukuk âlimi ve büyük edip ve tarihçi olan Ebu Ali El-Kâli gibi bazı meşhur âlimler bu şehirden yetişmiştir.