Жестокость инквизиторов спровоцировала восстание павликиан в городе Циносхора. Они казнили инквизиторов, после чего бежали в Арабский халифат, в мусульманскую часть Армении, и основали при посредничестве эмира свою колонию близ Милитены. Сарацины дружественно приняли павликиан как врагов Византийской империи и выделили им для проживания город Аргаум. Продолжающиеся преследования павликиан в Византии вынуждали все большее их число переселяться в Арабский халифат. Вскоре сюда переселился и Сергий. Павликиане сформировали внушительную силу. Временами они совершали набеги на соседние провинции, в ходе которых уводили пленников, пытаясь обращать их в свою веру. Сергий пытался отговорить от этого своих сторонников, но его не всегда слушались. Он погиб в 835 г.: во время лесорубных работ его убил фанатический приверженец греческой церкви. После смерти Сергия община получила республиканский строй, пока гонения с приходом к власти императрицы Феодоры (842–867 гг.) не увеличили их числа, дав им и способного полководца и главу в лице Карвеаса (Карбея), который построил на берегу Евфрата в Западной Армении крепость Тефрику (ныне – турецкий город Дивриги), ставшую столицей государства павликиан. Им удалось временно создать независимое от Византии и Арабского халифата государство, куда стекались беглые крестьяне и городская беднота. Отсюда павликиане совершали успешные набеги на Византию и разбивали выходившие против них отряды. Во время одного из походов им удалось взять Эфес, превратив его церковь св. Иоанна в конюшню. Во время этого похода павликиане захватили в плен много священнослужителей. Для организации обмена пленными император Василий I Македонянин (867–886 гг.) в 868 г. отправил к павликианам послом ученого монаха Петра Сицилийского. Он прожил девять месяцев среди павликиан и позднее описал собранные им факты в книге, которая по сегодняшний день является основным источником по их истории. Договориться о мире Византии и павликианам не удалось. Император Василий I, встревоженный их силой, организовал поход на Тефрику, но он закончился неудачей, а павликиане, в ходе успешной контратаки, захватили Анкару. Одновременно они организовывали походы против армян и арабов. В конце концов, зятю Василия I – Хрисофору в 872 г. удалось разбить государство павликиан и захватить Тефрику. Лидер павликиан – Хрисохер, пасынок и наследник Карвеаса, при этом был захвачен и обезглавлен. По всей Западной Армении было умерщвлено около 100 тыс. павликиан: многие из оставшихся бежали в Восточную Армению и объединились с армянским движением тондракийцев (христианско-гностическая секта, возникшая в Армении в середине IX в., отрицавшая бессмертие души и во многом носившая антифеодальный характер). Несмотря на это, сообщества павликиан в Византии продолжали существовать. Императоры Константин VII Порфирородный (912–920 гг.) и Иоанн I Цимисхий (969–976 гг.) переселили часть павликиан во Фракию, около г. Филиппополя, где в обмен на свободу вероисповедания они были обязаны сдерживать наступления на Византию скифов. Их использовали и как заслон от давления ислама. Павликиане прожили здесь в полной независимости около столетия, пока император Алексей I Комнин (1081–1118 гг.) не наказал их за оставление его знамени в норманнскую войну. В 115 г. он встал на зимние квартиры у Фелиппополя, чтобы обратить их в православие силой оружия. В непосредственной близости от колонии павликиан был основан верный православию и императору город Алексиополь.