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