Но и это был еще не конец. В 645 году Констант II и его советники запоздало отправили флот, чтобы вернуть Александрию. Амр оставил в городе немногочисленный гарнизон, и византийцы смогли высадиться и без особого труда захватить город. Узнав об этом, Амр двинулся туда с большим войском. На этот раз ворота были закрыты, а стены защищали, поэтому ему пришлось идти на штурм с осадными машинами и катапультами. Сделав пробоину, войска мусульман проникли за стену, и сопротивление византийцев было подавлено. Мануил Аршакид, командовавший флотом, был убит, а уцелевшие корабли отплыли в Константинополь. Византийцы вернулись к ситуации 620 года, когда все восточные провинции были утрачены, только на этот раз навсегда.
В течение ближайших нескольких лет ситуация продолжала ухудшаться. Став полновластными хозяевами побережья Сирии и Египта, арабы начали строить свой флот. Будучи жителями пустыни и не имея соответствующего опыта, они использовали местную рабочую силу и местных же набирали в корабельные команды, и очень скоро их флот готов был выйти в море. В 649 году под руководством арабского правителя Сирии, Моавии, он напал на византийский остров Кипр и захватил и разрушил город Констанцию, древний Саламин. Спустя несколько лет арабы высадились на Родосе. Их пребывание там было недолгим, но они увезли с собой ценную добычу: остатки колосса, бронзовой статуи бога солнца Гелиоса, имевшей 32 метра в высоту. Одно из семи чудес света, она рухнула после землетрясения в 228 году до н. э. и с тех пор лежала на земле. Ее распилили на части, вывезли и пустили на переплавку. А в следующем году Моавия нацелился на Константинополь. Его флот захватил Халкидон и готовился пересечь Босфор, но был рассеян штормом…
Рано или поздно, но византийцам предстояло встретиться с арабами на море лицом к лицу. В 655 году Моавия начал строить в сирийском Триполи другой флот. Дело осложнилось тем, что византийские пленники, содержавшиеся в городской тюрьме, взбунтовались и вырвались наружу. Они побежали вниз, к берегу, подожгли склады и инструменты, а потом захватили несколько судов и отплыли в направлении Константинополя. Несмотря на эту неудачу, Моавия продолжил стрительство, а потом направил свои корабли для атаки на города южного побережья Малой Азии. Констант II, теперь уже молодой человек в возрасте за 20, ждал с византийским флотом и встретил арабов близ портового города Финикс, но арабский флот взял в этом бою верх. По свидетельствам, море было красным от крови византийцев, и один из тех, кто поднял восстание в Триполи, умолял императора бежать. Констант отдал царские одежды другому человеку, а сам спешно покинул флагман, перейдя на меньшее быстроходное судно, и скрылся на нем. Тот же, кто взял плащ императора, стоял на носу флагманского корабля и сражался, пока его не окружили и не убили. Констант благополучно прибыл в Константинополь, но флот был разбит, и оставалось только гадать, как долго еще столица будет безопасным местом пребывания. В 626 году персы и авары не смогли взять ее, потому что не имели кораблей. Теперь же это был только вопрос времени, когда арабский флот вновь войдет в Босфор. С тревогой смотрел Констант со стены, обращенной к морю, на юг, где на горизонте рано или поздно должны были появиться вражеские корабли.