Казалось, что в Малой Азии, почти целиком завоеванной сельджуками, обстоятельства складывались благоприятно для империи, так как среди малоазиатских турецких правителей (эмиров) шла междоусобная борьба за власть, что ослабляло турецкие силы и приводило страну в состояние анархии. Но Алексей не мог направить всего своего внимания на борьбу с турками ввиду нападений на империю с севера печенегов.
Последние в своих действиях против Византии нашли союзников внутри империи в лице живших на Балканском полуострове павликиан. Павликиане представляли собой восточную дуалистическую религиозную секту, одну из главных отраслей манихейства, основанную в III веке Павлом Самосатским и преобразованную в VII веке. Живя в Малой Азии, на восточной границе империи, и твердо отстаивая свое вероучение, они были вместе с тем прекрасными воинами, доставлявшими немало хлопот византийскому правительству. Как известно, одним из излюбленных приемов византийского правительства было переселение различных народностей из одних областей в другие, так например, славян в Малую Азию, а армян на Балканский полуостров. Подобная судьба постигла и павликиан, которые в большом количестве были переселены с восточной границы во Фракию в VIII веке Константином V Копронимом и в X веке Иоанном Цимисхием. Центром павликианства на Балканском полуострове сделался город Филиппополь. Поселив восточную колонию в окрестностях этого города, Цимисхий, с одной стороны, достиг удаления упорных сектантов из их укрепленных городов и замков на восточной границе, где с ними трудно было справляться; а с другой стороны, он рассчитывал, что на месте нового поселения павликиане будут служить крепким оплотом против частых нападений на Фракию северных «скифских» варваров. В X же веке павликианство распространилось по Болгарии благодаря преобразователю этого учения попу Богомилу, по имени которого византийские писатели называют его последователей богомилами. Из Болгарии богомильство позднее перешло в Сербию и Боснию, а затем и в Западную Европу, где последователи восточного дуалистического учения носили различные названия: патарены в Италии, катары в Германии и Италии, побликаны (т.е. павликиане) и альбигойцы во Франции и т.д.
Византийское правительство, однако, ошиблось в своих расчетах на роль поселенных на Балканском полуострове восточных сектантов. Во-первых, оно не предполагало возможности быстрого и широкого распространения ереси, что на самом деле случилось. Во-вторых, богомильство сделалось выразителем национальной славянской и политической оппозиции против тяжелого византийского управления в церковной и светской областях, особенно в пределах покоренной при Василии II Болгарии. Поэтому вместо того, чтобы защищать византийские пределы от северных варваров, богомилы призывали печенегов для борьбы против Византии. К печенегам присоединились куманы (половцы).
