Η δράση των πρώτων Παυλικιανών εξόργισε τον Αρμένιο πατριάρχη Ναρσή Γ', ο οποίος ξεκίνησε διώξεις εναντίον τους. Έτσι, ο Κωνσταντίνος και οι οπαδοί του, αναζήτησαναφού πρώτα συμμάχησαν με τους Άραβες ενάντια στους μονοφυσίτες του Ναρσή (Αναστασίου Ιωάννης, ''Οι Παυλικιανοί'', σ. 44), καταφύγιομπήκαν σεστο βυζαντινό έδαφος και συγκεκριμένα στην πόλη Κίσοβα, κοντά στην Κολώνεια. Στη νέα του έδρα, ο Κωνσταντίνος υιοθέτησε το όνομα ενός από τους μαθητές του [[Απόστολος Παύλος|Αποστόλου Παύλου]], του Σιλουανού. Επίσης ονόμασε την κοινότητά του "Μακεδονία". Τελικά, προσείλκυσε την προσοχή του αυτοκράτορα [[Κωνσταντίνος Δ'|Κωνσταντίνου Δ' Πωγωνάτου]] (668-685), ο οποίος απέστειλε τον αξιωματούχο του Συμεών στην Κίβοσα με τη ρητή εντολή να εκτελέσει τον Κωνσταντίνο-Σιλουανό. Πράγματι, ο Συμεών τον συνέλαβε και εξανάγκασε τους οπαδούς του να τον λιθοβολήσουν μέχρι θανάτου. Οι Παυλικιανοί παραδόθηκαν στην [[Ορθόδοξη Εκκλησία]] για κατήχηση. Ωστόσο, προσποιήθηκαν ότι προσηλυτίσθηκαν και διατήρησαν την κοινότητά τους στην Κίβοσα. Εκεί επέστρεψε ο Συμεών έπειτα από παραμονή τριών ετών στην [[Κωνσταντινούπολη]]. Τελικά τον είχε κερδίσει η παυλικιανή διδασκαλία την οποία είχε γνωρίσει κατά τη διάρκεια της ανάκρισης του Κωνσταντίνου-Σιλουανού. Κατά μία ειρωνεία της τύχης, από διώκτης έγινε ο νέος διδάσκαλος των Παυλικιανών. Η δράση του Συμεών-Τίτου διακόπηκε απότομα, όταν ο αυτοκράτορας [[Ιουστινιανός Β']] (685-695 και 705-711) στράφηκε εναντίον του. Ο Διδάσκαλος και οι άλλοι Παυλικιανοί που δεν απαρνήθηκαν την πίστη τους παραδόθηκαν στην πυρά. Ο Παυλικιανισμός κινδύνευε με αφανισμό μόλις λίγα χρόνια μετά την ίδρυσή του.
Τον Παυλικιανισμό διέσωσε ο νέος διδάσκαλος Παύλος ο Αρμένιος. Μαζί με άλλους ομοϊδεάτες του, διέφυγε στην Επίσπαρη, κοντά στην [[Αμάσεια]] του [[Πόντος|Πόντου]], όπου προχώρησε σε ανασύνταξη των δυνάμεων της αίρεσης. Ήταν τόσο σημαντικός ο ρόλος του, ώστε πολλοί ιστορικοί πιστεύουν ότι το όνομα της αίρεσης προήλθε από εκείνον και όχι από τον [[Απόστολος Παύλος|Απόστολο Παύλο]].
