Завоевание арабами-мусульманами византийского Ближнего Востока и остатков персидской империи произошло уже после смерти Мухаммеда: он дал импульс, а основные завоевания были совершены его преемниками и последователями. Ближний Восток был завоеван при первом преемнике Мухаммеда – халифе Омаре. В 634 г. арабы взяли Газу – процветающий приморский греческий город на границе Египта и Палестины. Византийцы уже начали воспринимать новых противников всерьез, и в этом сражении во главе войска стоял брат императора Ираклия, но он был разбит и бежал в Эдессу. В 636 г. была захвачена почти вся Палестина, совсем недавно разоренная и опустошенная персами и с таким трудом отвоеванная. В конце года началась осада Иерусалима. Город держался больше года, а в конце концов был, по сути дела, сдан святым патриархом Софронием (638 г.), который смог предварительно договориться с мусульманами о сохранении жизни христиан и об отказе от разрушения христианских храмов: память о персидском погроме была еще слишком свежа. Крест Господень и многие христианские святыни удалось вывезти в Константинополь. Арабское завоевание кардинально изменило этническую и религиозную картину Палестины и в целом Ближнего Востока, но настоящего погрома всего христианского и византийского, который предпринял Хосров, больше не повторилось. Однако эпоха греческой гегемонии в этом регионе ушла в прошлое. Греческие общины, кварталы, монастыри сохранялись (они сохраняются так или иначе до сих пор в Израиле, Египте, Иордании), но живая связь с митрополией (в данном случае с Византией) оказалась прервана, начался постоянный отток греческого населения. С 636 по 642 г. арабы смогли отторгнуть от византийской империи все недавно возвращенные Ираклием провинции: Месопотамию, значительную часть Сирии, Палестину, Египет и Киренаику (в 642 г. была взята Александрия). По ходу войны Ираклий назначил в 638 г. соправителем своего двенадцатилетнего сына Ираклия и умер в начале 642 г. почти что в семидесятилетнем возрасте. Соправителями после его смерти остались юный Ираклий II и старший сын Константин, переживший отца всего на несколько месяцев. После этого империя на время погрузилась в круговорот внутренних проблем.
На этом арабская экспансия не завершилась, и еще ни раз византийцам приходилось видеть арабов под стенами своей столицы. Новый этап начался с освоением арабами морского дела. Это произошло быстро, и в 649 г. «сарацины», как их называли христианские авторы, захватили Кипр. В 50-е гг. они захватили Армению и Родос и впервые подвергли длительной осаде Константинополь. На этот раз осада была снята из-за внутренних неурядиц в халифате. В 659 г. был заключен мир, который продержался всего десять лет. Незадолго до того, в 651 г., был убит последний шах сасанидской Персии – Издегерд III. Интересно, что похоронен он был в Меровском оазисе по христианскому обряду. Теперь для византийцев место их бывшего главного врага прочно занимал куда более динамичный арабский халифат, расположенный в тех же областях, что и Персидская империя.
В начале 70-х гг. арабы захватили у византийцев Кизик и Смирну, а в 674 г. начали новую осаду Константинополя, которая продолжалась семь лет. В 678 г. византийцы впервые применили против арабского флота «греческий огонь» – состав, содержавший нефть и селитру, который выбрасывался на вражеские корабли в закрытых сосудах с помощью специальных устройств и воспламенялся уже там. Этот огонь нельзя было потушить водой, поэтому против вражеских флотов, в особенности варварских, это всегда действовало не только эффективно, но и устрашающе. В 680 г. между византийцами и арабами был заключен тридцатилетний мир, который продержался, впрочем, чуть более десяти лет.
В 692 г. император Юстиниан II попытался выступить против арабов в союзе со славянами. Начало было удачным, но после ухода славян император был вынужден отступить. В 697 г. был захвачен Карфаген, последний византийский оплот в северной Африке, а флот разгромлен. Римская Африка была утеряна навсегда. Своего рода попыткой ее восстановления станет эпопея французской колонизации XIX–XX вв.