Остальные епископы Мелитины позднеантичной и средневековой эпох известны исследователям, в основном, лишь по их подписям под актами различных Соборов Константинопольской православной церкви. В период завершения формирования иерархии Константинопольской православной церкви (в V–VI вв.) в списках кафедр патриархата митрополия Мелитины заняла 13-е место. В состав этой митрополии на территории провинции Армения Вторая (затем Третья) входили епископские кафедры Арависс, Ариаратия, Арка, Комана, Барид, Губос, Калудия, Хесн-Патрик, Аромана, Созопетра (Тела-Кастра). После начала арабских завоеваний и разорений Малой Азии в VII в. большинство этих кафедр были лишь титулярными. В 635 г. арабы-мусульмане впервые попытались захватить Мелитину, но были вскоре изгнаны византийским войском императора Ираклия. В 656 г. город был впервые взят арабами, и в нём был размещён их гарнизон. Мелитина начала играть роль одного из передовых укреплений мусульман, опираясь на которое они могли вести нападения как на Византию, так и на Армению и Закавказье. В конце VII – VIII вв. византийцам удалось несколько раз на краткое время вернуть Мелитину, но эти события сопровождались разрушением оборонительных стен и выводом оставшегося населения в более безопасные области империи. Городская жизнь в Мелитине к этому времени фактически прекратилась; город превратился в пограничную крепость, которая неоднократно переходила из рук в руки в многовековой войне между христианами и мусульманами на Ближнем Востоке. Наибольшего политического значения Мелитина достигла в 830–860 гг., когда здесь образовался полунезависимый мусульманский эмират, глава которого Умар аль-Акта неоднократно совершал нападения на Византию, но в 863 г. был убит в битве при Лалакаоне (область Понт, север Малой Азии), в которой византийский император Феофил почти полностью уничтожил арабское войско. В конце IX – начале X вв. в ходе начавшейся византийской реконкисты на Ближнем Востоке византийцы неоднократно пытались осаждать Мелитину, но терпели неудачи; город и его предместья страдали от разграблений и пожаров. В 934 г. Мелитина была захвачена войском византийского доместика Иоанна Куркуаса и стратига фемы Ликанд Мелия. С этого времени до начала XII в. продолжалось христианское правление. Мусульмане были изгнаны из Мелитины либо принуждены были принять крещение; в городе расселились греки и армяне. Мелитина и её регион (как и большинство других захваченных у мусульман областей) были поставлены под прямое императорское управление в качестве куратории, части императорского домена, в которой собственность на землю принадлежала лично императору.