Победа над павликианами не должна быть рассматриваема как событие внутренней политики. Напротив, это был значительный успех во внешней политике, близко затронувший интересы мусульманского элемента. В течение IX в. арабы продвинулись далеко на запад, прежние границы с Персией — Дара и Нисиби — давно уже были забыты и отошли к мусульманским владениям. Теперь граница между византийскими и арабскими пределами, часто, впрочем, нарушаемая и поддающаяся то в одну, то в другую сторону, шла по горам Тавра на юге до фемы Ликанда, затем проходила в восточном направлении и, оставляя во власти мусульман Малатию, или Мелитену, направлялась к юго-восточному берегу Черного моря по границе Армении. Несомненно, арабам принадлежали здесь многие исконные византийские области, постепенно подвергавшиеся колонизации турецкими племенами. Малатия-Мелитена, составлявшая наиболее вдавшийся в византийские провинции укрепленный мусульманский город, бывший столицей самостоятельного эмира, который оказывал поддержку павликианам, была теперь первой и естественной целью византийского правительства после срытия Тефрики и уничтожения павликианских городов. И тем настоятельней было не медлить осуществлением этой цели, что часть павликиан перебралась из византийских областей в арабские и нашла защиту у мусульман. Таким образом, на весну 873 г. решен был новый поход на Восток, имевший целью мусульманский пограничный город Малатию, до которого теперь доходила граница между греками и арабами.
Прежде чем приступить к осаде Малатии, царь Василий, сам принявший на себя главное начальство над войском, решился овладеть другими пограничными крепостями и, смотря по надобности, сровнять их с землей или укрепить их. Таковы были Запетра и Самосат на Евфрате, часто упоминаемые в истории войн империи с персами и арабами. При взятии Запетры в руки победителей досталась богатая добыча и освобождено было много христиан, томившихся в плену; без особенных затруднений взят был и Самосат, большой город на Евфрате. После этих военных успехов царь подступил к Малатии, которую, впрочем, предстояло брать осадой. Здесь ожидали царя большие неприятности: прежде чем началась правильная осада города, арабский вождь Ахмед ибн-Мохаммед ал-Кабус нанес грекам поражение и убил одного из главных воевод Василия, патрикия Насра (4). Испытав неудачу в этом предприятии против Малатии, царь Василий опустошением занятой прежде павликианами области вознаградил себя за понесенное поражение и при возвращении в столицу назначил себе триумфальный въезд.
Граница между арабами и византийцами, как сказано выше, шла по горам Тавра. Здесь возникло несколько укреплений, имеющих назначением защищать дорогу через Киликийское ущелье из Тианы в Таре. Особенное значение получило здесь укрепление Лулу, построенное греками, но отнятое у них арабами и вновь сильно укрепленное (5). Защита этого важного пограничного укрепления вверена была славянам, давно уже поселенным в Малой Азии, которые с переходом местности под власть арабов сохранили за собой права и обязанности, соединенные с охраной этой важной позиции, находясь в непосредственной зависимости от эмира Тарса. Нужно думать, что славянская колония пользовалась известными привилегиями и денежными субсидиями от арабского пограничного правителя, который не всегда исполнял свои обязательства и лишал славянских граничар идущего им содержания. С своей стороны царь Василий обещанием славянам новых привилегий и денежных выдач старался привлечь их на сторону Византии и побудить к сдаче крепости. Но так как названная крепость имела чрезвычайно важное значение, то калиф Мутамид нашел необходимым сменить прежнего правителя Тарса, который возбудил своими действиями недовольство славян, и назначить на его место Ахмеда ибн-Тулуну, основателя правящей династии в Египте. Вместе с этим Египет и Сирия подпали под власть египетских Тулунидов и составляли до 905 г. одно княжество. Но временный успех византийской политики в горах Тавра сопровождался дальнейшим движением против мусульман. Вслед за Лулу на сторону Византии переходит другое пограничное укрепление, Мелдос, или Милос. Можно думать, что военное предприятие против арабов не ограничивалось указанными местами, но шло по всей границе. Так, находим указание на одновременные с этим действия византийских отрядов в прежней области павликиан, близ Тефрики, где был взят город Катаватала и др. Эти успехи, относящиеся к 877 г., доставили грекам некоторое преобладание на восточной границе и позволили Василию решительней выступить против арабов в ближайшие годы. В 878 г. было сделано арабами нападение на Южную Каппадокию (фема Анатолика). Хотя страна была опустошена и много людей было взято в плен, но греки напали на неприятеля, обремененного добычей, и нанесли ему полное поражение. Сам предводитель захвачен был в плен и послан в Константинополь, а из всего 4-тысячного отряда спаслось не более 600 человек. В 879 г. византийские предприятия распространяются еще далее. Жизнеописатель Василия говорит по этому поводу: