Պավլիկյանները ոչ միայն իրենց գաղափարներով, այլև ռազմական գործողություններով լուրջ վտանգի ենթարկեցին Բյուզանդական կայսրության գոյությունը: Ուստի բյուզանդական արքունիքը IX դ. կեսերին ուժեղացրեց պատժիչ գործողությունները պավլիկյանների դեմ: Մի պահ նրանք անգամ ստիպված եղան թողնել կայսրության սահմանները և ապաստանել արաբական տիրույթներում: Արաբական խալիֆայությունը սիրով նրանց ապաստան տվեց և բնակեցրեց սահմանամերձ շրջաններում: Նրանք մտադիր էին հայ պավլիկյանների ուժերն օգտագործել Բյուզանդիայի դեմ իրենց պայքարում:
Բյուզանդական զորքերն անխնա ոչնչացնում էին պավլիկյաններին՝ նպատակ ունենալով արմատախիլ անել շարժումը: Հենակետ դարձնելով Տևրիկ ամրոցը՝ պավլիկյանները ոչ միայն պաշտպանվում էին, այլև դիմում լայն հարձակողական գործողությունների: Պավլիկյանները վճռական պայքարի դիմեցին, երբ նրանց զինված ուժերի գլուխ անցավ տաղանդավոր զորավար Կարբեասը: Նրա ղեկավարությամբ պավլիկյանները փայլուն ու տպավորիչ հաղթանակներ տարան բյուզանդական կանոնավոր զորքերի դեմ և կարողացան անգամ դուրս գալ Սև ծովի ափերն ու մոտենալ կայսրության մայրաքաղաքին: Շարժման մասնակիցների թիվը կտրուկ աճեց:
Կայսրությունն ստիպված եղավ կենաց-մահու պայքար մղել անհաշտ թշնամու դեմ: Գահ բարձրացած հայազգի կայսր Վասիլ Ա-ն դիմեց վճռական գործողությունների: Նրա բանակները 872թ.՝ ծանր կռիվներից հետո, ջախջախիչ պարտության մատնեցին պավլիկյաններին և ավերեցին Տևրիկ ամրոցը՝ պավլիկյանների վերջին հենակետը:
Կայսրությունը պավլիկյաններին հոծ խմբերով տեղափոխեց Բալկաններ, որտեղ նրանք շարունակեցին տարածել իրենց գաղափարները: Նրանց ազդեցությամբ Բուլղարիայում ծնունդ առավ բոգոմիլների, իսկ Ֆրանսիայում ալբիգոյանների շարժումները: