Положение арабов в Египте еще не было достаточно прочным. Император Констант II не хотел примириться с потерей своей богатейшей провинции. В 645 г. византийский флот из 300 кораблей неожиданно появился у стен Александрии. Арабский гарнизон насчитывал всего тысячу воинов, и не смог оказать сопротивления.

Захватив Александрию, византийцы под командованием Мануила двинулись к Фустату. Сражение с армией Амра закончилось разгромом византийского войска. В конце 645 или в самом начале 646 г. арабы вновь овладели Александрией: город был разорен, укрепления, закрывавшие подступы с суши, срыты. Долгое время считалось, что Амр сжег знаменитую Александрийскую библиотеку, насчитывавшую около 700 тысяч томов. Однако ни мусульманские, ни христианские исторические хроники не упоминают о гибели библиотеки. Зато в легендах, сложившихся в мусульманской среде в более позднее время, халиф и его полководец предстают как великие ревнители веры, уничтожившие книги, содержавшие сведения, противоречащие священному Корану.

Овладев Александрией, арабы упрочили свое положение в Египте и вступили в борьбу с византийским господством на Средиземном море.

Халиф Омар запрещал правоверным выходить в море, хотя арабы еще до принятия ислама занимались мореплаванием. При Османе арабы, используя опыт сирийских и египетских кораблестроителей, создают флот, базой которого, наряду с портами Сирии, служила Александрия.

В 649 г. корабли арабов подошли к принадлежавшему Византии острову Кипр и покорили его главный город Констанцию. Арабам не удалось удержать остров, но берега Малой Азии оказались под постоянной угрозой морских набегов. В 654 г. арабы высадились на острове Родос. Одно из семи «чудес света» – колоссальная бронзовая статуя бога Солнца Гелиоса, установленная в III в. до н. э. при входе в гавань, лежала в руинах, разрушенная землетрясением. О ее размерах можно было судить по обломкам: редко кому удавалось обхватить даже один палец на руке гиганта. До наших дней не сохранилось никаких следов этого грандиозного сооружения. Считается, что арабы продали остатки статуи купцу из г. Эдессы, который нагрузил ими 900 верблюдов.

Византийская провинция Африки (Тунис и восточная часть Алжира) также подверглась набегу армии добровольцев, посланных Османом. По пути к ней присоединились вооруженные отряды из Египта и кочевники-берберы, населявшие Триполи. Взяв столицу Африки Карфаген, арабы ограничились контрибуцией и покинули город.