Стабильная христианская община окончательно сформировалась, как полагают исследователи, к середине IV в. Около 358 г. в Мелитинах состоялся Собор, в котором участвовали епископы из Каппадокии, из армянских провинций и некоторых других областей востока Малой Азии. Собор постановил низложить епископа Евстафия Севастийского и возвести на кафедру Севастии Мелетия (см. Мелетий I, архиепископ Антиохийский), уроженца Мелитины. Кто занимал кафедру в самой Мелитине в это время, исследователям неизвестно. Осенью 363 г. епископ Ураний из Мелитины участвовал в Антиохийском Соборе, на котором значительная часть восточного епископата подтвердила свою приверженность к Никейскому Символу веры. В 370 гг. кафедру Мелитины занимал Отрий, который состоял в переписке с Василием Великим, а также участвовал во втором Вселенском Соборе в Константинополе в 381 г. Около 377 г. в Мелитине родился Евфимий Великий, один из основателей палестинского монашества. Здесь же он был рукоположён во священника и провёл первые 30 лет жизни. Наставниками Евфимия Великого были Акакий и Синодий, оба ставшие впоследствии епископами Мелитины. Преемником епископа Отрия был епископ Летоий, который известен исследователям по одному из посланий, отправленных ему Григорием Богословом. Акакий из Мелитины сыграл значительную роль в жизни восточных церквей в 430 гг. Он одним из первых обличил ересь Нестория, участвовал в третьем Вселенском Соборе в Эфесе в 431 г., состоял в переписке с Кириллом Александрийским. Епископ Константин из Мелитины в 448 г. участвовал в Константинопольском Соборе, на котором под председательством Константинопольского архиепископа Флавиана было впервые осуждено евтихианство (монофизитство). В 449 г. на Эфесском Соборе епископ Константин отсутствовал по не известной исследователям причине, и вместо него делегацию из провинции Армения Вторая возглавляли епископы Иоанн Никопольский и Акакий Ариаратийский. Однако в 451 г. епископ Константин участвовал в четвёртом Вселенском Соборе в Халкидоне и подписал его акты. Епископ Отрий (II) в 458 г. подписал «Энкиклион» византийского императора Льва I, в котором осуждал убийство монофизитами Александрийского патриарха Протерия. Среди епископов Мелитины в конце VI в. особую роль в политической жизни Византии сыграл Дометиан, двоюродный брат византийского императора Маврикия (582–602 гг.). Епископ Дометиан жил, в основном, в Константинополе и, как полагают исследователи, выполнял роль духовного наставника императорской семьи армянского происхождения. Также выполнял ответственные поручения императора; в 591 г. сопровождал из Сирии в Ктесифон персидского шаха Хосрова II, который был возвращён на персидский престол византийским войском.