Zdaniem bizantyjczyków nazwa „paulicjanie” pochodziła od Pawła z Samosaty, biskupa żyjącego w III wieku. Paweł i jego brat Jan mieli propagować w Samosacie manicheizm, religię swojej matki, Kallinike. W połowie VII wieku , Ormianin pochodzący z Mananali, w czasie swoich podróży natknął się na Diakonusa, wyzwoleńca z Syrii, zaangażowanego w samosacką gminę. Zasady wiary głoszone przez Diakonusa oczarowały Konstantyna i osiedlił się on na jakiś czas w Samosacie, aby pobierać nauki. Następnie powrócił do Mananali, gdzie rozpoczął działalność misyjną wśród swoich rodaków. Udało mu się zdobyć niewielką grupę zwolenników, z którą przeniósł się do Kibossy, nieopodal Kolonei, gdzie liczba jego zwolenników wzrosła. Konstantyn i jego uczniowie mieli zdominować Kibossę, a ich kościół działał tam dwadzieścia siedem lat, dopóki nie został wykryty przez władze.