В 40-е гг. начинаются также вторжения арабов в Малую Азию. В это же время арабы постепенно овладели городами сиро-палестинского побережья, еще продолжавшими сопротивление. В 641 г. пала Кесария Приморская, выдерживавшая осаду в течение 7 лет (с перерывами).

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

Вслед за Кесарией настала очередь Аскалона. Город долго и упорно сопротивлялся и пал лишь в 644 г. или в самом конце 643 г. Относительно обстоятельств его взятия источники молчат.

Констант II не предпринимал, по-видимому, никаких попыток отбить у врага сиро-палестинское побережье. А тем временем арабы приступили к созданию на Средиземном море своего военного флота. Инициатором морских походов против ромеев явился Муавия-ибн-Абу-Суфьян. Еще в 642 г. он предложил халифу Омару организовать поход на Кипр. Осторожный Омар отклонил это предложение, так как считал морские экспедиции по Средиземному морю слишком рискованными. Однако Муавия не оставил своего намерения и, когда после смерти Омара в 644 г. халифом стал Осман, приходившийся ему родственником, снова выступил с инициативой организации морских походов. После некоторых колебаний Осман согласился. В прибрежных городах был построен флот, который через некоторое время смог соперничать с византийским флотом. Его основной базой стал город Акка (Акра). В 646 г. Осман назначил Муавию правителем всей Сирии, включая ал-Джазиру, Финикию и Палестину. Муавия был также наделен правом ведения войны и заключения мира с византийцами по собственной инициативе.

Прежде всего он послал войско, которое взяло финикийский город Триполи. К началу 40-х гг. VII в. арабы постепенно приобрели определенный опыт по осаде городов. Поэтому при штурме Триполи они действовали одновременно с суши и моря, забрасывая город камнями из множества метательных машин. Когда в городской стене образовалась брешь, часть осаждающих ворвалась в нее, в то время как другие по лестницам поднялись на верх стены. После трехдневных боев арабы полностью овладели городом.