Originally from Armenia, the Paulician sect spread to the eastern provinces of the Byzantine Empire by the seventh century. The Paulicians met with strong persecution here, especially under the short reign of Empress Theodora who killed around 100,000 Paulicians.
The Council of Dvin in 719 produced more persecution for the Paulician Gnostics, but many sects continued to thrive. The Paulicians in Armenia even managed to ally with the Muslims in response to the Byzantine Emperors. By 844, the sect established a Paulician state at Tephrike (in present-day Turkey) under the leadership of a man named Karbeas. Unfortunately, the power of this state ended in 871 under Emperor Basil I. The survivors of this struggle re-located to Syria and Armenia.
In 970, the remaining Paulicians in Syria were deported to the Balkans. Here, the removed Paulicians combined with another Medieval Gnostic sect, the Bogomils. Similarly, the Paulicians that originally fled back to Armenia joined with the Tondrakians.