Согласно преданию, сохраненному мусульманскими источниками, Умар не дал Муавийе разрешения на выход в море, однако его преемник Усман снял запрет, снабдив позволение любопытным условием: Муавийя должен был взять с собой жену — очевидно, чтобы она удержала его от безрассудного риска. И его, и многих других знатных мусульман сопровождали верные жены. После первого успешного набега население Кипра обязали выплачивать мусульманам ежегодную дань. Они уже платили дань Византии, так что остров оказался как бы под двойной властью, и обе стороны получали с него деньги, но не держали на нем постоянного гарнизона. В 654 году Муавийя повторил вторжение, потому что, как утверждали мусульмане, киприоты предложили Византии корабли для действий против мусульман, нарушив тем условия договора. Сообщается, что флот мусульман насчитывал 500 судов и нес 12 ООО воинов регулярной армии, то есть тех, чьи имена были внесены в «диван». Считается, что в этот раз Муавийя возводил на острове мечети и выстроил новый город, который заселил людьми с Баальбека, сделав из них гарнизон и назначив им жалование. Этот форпост мусульман продержался, пока сын Муавийи Йазид не вывел людей и не снес город: по-видимому, он счел неоправданными расходы на содержание гарнизона.

На всем протяжении VII, VIII и IX веков Кипр сохранял уникальное положение между мусульманским и христианским мирами. Удержать его не всегда оказывалось легко. Мусульманские законоведы недовольны были договором, который во многих отношениях нарушал закон ислама. Да и с военной точки зрения киприотов постоянно подозревали в оказании помощи Византии. Омейядский халиф Валид II депортировал многих киприотов в Сирию, заподозрив их в пособничестве византийцам, однако его преемник Йазид III позволил им вернуться. Проблемы сохранялись и при Аббасидах, а в 806 году, в царствование Гаруна аль-Рашида, на острове якобы начались народные волнения, и пришлось послать экспедицию, чтобы призвать островитян к порядку. Сообщают, что 16 000 пленников было вывезено в Ракку — поселение Гаруна в Северной Сирии. Оттуда их выкупили или продали в рабство, один епископ-киприот обошелся в 2000 динаров. Несмотря на эти осложнения, греческое христианство и соответствующая культура сохранились на острове и тогда, когда практически исчезли на большой земле. Второй Никейский собор состоялся в 787 году. Епископы из областей под властью мусульман не смогли прибыть на него, но от Кипра явились пять епископов, что доказывает по-прежнему тесные связи Кипра с Византией.

За первым набегом на Кипр последовали нападения на другие средиземноморские острова: Родос и Кос были разграблены, по всей вероятности, в 654 году. До этого времени мусульмане не сталкивались непосредственно с византийским флотом, который все еще оставался владыкой вод восточного Средиземноморья. Первое настоящее морское сражение между мусульманами и византийцами — так называемая «битва мачт» («Зат ас-саварн»), или битва при Фениксе, — случилась у Ликийских берегов в 655 году. Описания Ибн Абд аль-Хакама, греческой хроники Феофана и позднейшей арабской хроники Ибн аль-Атира дают нам сведений об этом сражении больше, чем о каком либо другом столкновении флотов того периода. Согласно арабским источникам, кампания началась с того, что император Констант II (641-668) подготовил морскую экспедицию против завоеваний мусульман в Северной Африке. Он вышел в море с флотом в 500 или 600 кораблей, «и людей на нем было больше, чем когда-либо собирали византийцы со времени прихода ислама». Муавийя послал Ибн аби Сарха, наместника Египта, который «начальствовал и над морем», перехватить их. Два флота сошлись у Л испанского побережья. Когда мусульмане впервые завидели византийцев, ветер для них был встречным, но затем настал штиль, и оба флота встали на якоря. Стороны договорились о перемирии на ночь; мусульмане читали Коран и молились, византийцы звонили в колокола. На следующее утро флоты сблизились, и мусульманские корабли сцепились с византийскими. Сражались мечами и кинжалами, и с обеих сторон было много убитых. В конце концов Всевышний оказался благосклоннее к мусульманам, император, получив рану, бежал с места сражения, и в живых остались лишь немногие византийцы. Ибн Аби Сарх оставался на этом месте еще несколько дней, после чего вернулся в Сирию.

Самый пространный отчет об этой битве дает нам Ибн Абд аль-Хакам, использовавший египетские источники, по-видимому, в Египте и собранные, так как в арабском флоте было много египтян, вернувшихся туда после сражения. Его описание, однако, сильно формализовано и разочаровывает тем, что слишком много места в нем уделено вопросам: кто на чьей дочери женился после битвы, и другим, малоинтересным для историка флота обстоятельствам. Из его отчета удается извлечь, что морское сражение было частью совместной операции и что половина корабельных команд оставалась в то время на суше. У византийцев было 1000 кораблей против 200 мусульманских. Командующий, Ибн Аби Сарх, созвал военный совет, на котором один из выступавших ободрял собравшихся, говоря, что если поможет Всевышний, то и малым числом можно победить большое войско. Таким образом, мусульмане укрепились духом, и два флота стали сходиться. Бой начался выстрелами из луков. Император посылал гонцов узнать, как идет сражение. Услышав, что они сражаются луками и стрелами, он сказал, что византийцы наверняка победят; услышав затем, что сражающиеся бросают камни, он повторил, что византийцы побеждают, но услышав, что суда сцепились вплотную и люди сражаются на мечах, он предсказал победу арабов.

Греческий отчет Феофана рисует несколько иной фон событий. Согласно его хронике, Муавийя готовил флот для нападения на Константинополь. Пока в Триполи (Ливане) собирался флот, двое «христолюбивых братьев, сыновей трубача», взломали тюрьму в Триполи и освободили множество заключенных в ней византийцев. Затем они захватили город и убили правителя, после чего бежали во владения Византии. Однако Муавийю это не смутило, и флот под командой некого Абул-Авара в срок вышел в море. Император Констант вступил в бой у Феникса в Ликии, но, увы, он был плохо подготовлен к сражению. Скоро море наполнилось кровью византийцев, а император сбросил с себя царственное одеяние, чтобы скрыться незамеченным. Он бы погиб, если бы не один из сыновей трубача, который вытащил его из воды и погиб, спасая его.

Все отчеты сходятся в том, что «битва мачт» стала крупной победой мусульман и положила конец неограниченному господству византийского флота в восточном Средиземноморье. Увы, мы не видим более отчетливой картины происходящего. Более поздний историк, писавший об этом сражении, придерживается весьма невысокого мнения об обеих сторонах:

Источники в действительности слишком скудны, чтобы понять, заслуженны ли столь суровые упреки. Однако ясно, что мусульманский флот в целом все еще был слабее морских сил византийцев. Это стало особенно очевидно при нападении на Константинополь, которое началось в 674 году. Мусульмане с самого начала понимали, что невозможно взять город, не овладев прежде окружающими его водами. Большой арабский флот под командой сына Муавийи Йазида вошел в Мраморное море. В течение четырех лет он все лето блокировал город, уходя затем на зимовку в Кизик в южной части моря. Несмотря на столь неотступное давление, оборонявшиеся держались твердо. Византийцам помог так называемый греческий огонь, возможно, примененный тогда впервые. Изобрел его некий Каллиник, беженец из занятого арабами Баальбека в Сирии. Греческий огонь был смесью сырой нефти и других веществ, которые налипали на дерево. Его поджигали и распыляли из сифонов в сторону вражеских кораблей. Впрочем, учитывая, что византийцы получили формулу смеси от жителя Баальбека, не исключено, что изобретение это родом с Ближнего Востока. Но есть указания, что мусульмане применяли этот огонь и при первой осаде города.