Хотя мы не знаем точной даты начала служения Константина из Мананалиса, историки обычно относят ее примерно к 655 году. По словам историков Джанет и Бернарда Гамильтон, он с самого начала действовал так, как если бы:

«… восстанавливал истинную церковь, основанную св. Павлом… Следующие didascaloiследовали примеру Константина и брали имена учеников св. Павла; они также называли свои церкви в честь тех мест, которые посещал Св. Павел. В результате они как бы восстанавливали истинную апостольскую церковь».

Разумеется, эти еретики называли себя просто «христианами» (эта черта была у них общей с богомилами и катарами, которые тоже называли себя «добрыми христианами»). Название «павликиане», очевидно, не имело ничего общего с их преданностью учению св. Павла, но вошло в употребление спустя долгое время после образования секты и использовалось другими людьми. Скорее всего оно происходит от дидасколоса Павла, который привел полукочевую секту обратно в Армению в VIII веке.

Хотя павликиане считали себя истинными христианами, православная церковь и Византийская империя придерживались иного мнения. Константина из Мананалиса в конце концов казнили за ересь по приказу императора Константина IV (668–685). По мнению историков, его скорее всего сожгли на костре, хотя сами павликиане распространяли историю о том, что он был забит камнями до смерти. Возможно, это было сделано с целью «провести аналогию между их первомучеником и первым христианским диаконом Стефаном».

Второй павликианский дидасколос, который взял себе имя Тит, тоже был казнен за ересь; на этот раз смерть на костре не вызывает сомнений.

В VIII веке н. э. павликиане довольно долго пользовались официальной терпимостью со стороны церкви, хотя Иоанн («Философ») Отцунский, который стал католикосом Армении в 717 году, говорил о них как о «злокозненной секте «отбросов», которые называют себя павликианами». Больше всего его возмущал тот факт, что они презирали служителей официальной церкви как «идолопоклонников из-за их преклонения перед крестом», но, по-видимому, он не прибегал к поддержке светских властей для того, чтобы изменить такое положение вещей.

Лишь при византийском императоре Михаиле I (811–813) для сторонников павликианского вероучения была восстановлена смертная казнь. За этим последовал период массовых гонений, за время которого, согласно официальным летописцам, погибло около 100 000 еретиков. Такой масштаб резни был сопоставим с побоищем, учиненным над катарами из Лангедока 400 лет спустя. В 840-х годах в ответ на непрестанные гонения часть павликиан, включавшая боевой отряд численностью 5000 человек, отступила на арабские территории. В 850-х годах они основали свое независимое мини-государство со штаб — квартирой в укрепленном городе Тефрик на византийской границе. Именно туда, ко двору павликианского лидера Хрисохира в Тефрике, отправилось посольство Петра Сицилийского в 869–870 годах. Два года спустя Хрисохир был убит в бою с византийской армией, а Тефрик окончательно капитулировал в 877 году.

Однако это поражение павликиан еще не стало концом для них. Около 975 года они все еще доставляли достаточно неприятностей православной церкви в Византийской империи, чтобы она приняла решение о депортации большого количества павликиан из восточных провинций. Их послали на Балканы, где уже существовала старинная община павликиан, а Богомил начал распространять собственную ересь всего лишь несколько лет назад. Павликиане, почти несомненно, завещали богомилам свою веру в противоположность материального и духовного царства Бога Зла и Бога Добра. Более того, павликиане считали этот аспект своей системы верований главным фактором, отличавшим их от римско-католической и православной церкви. Они говорили Петру Сицилийскому:

«Мы говорим, что небесный отец — это истинный Бог, который не имеет власти в этом мире, но имеет власть в мире грядущем, и что есть другой Бог, который создал этот мир и наделен властью над ним.