После кончины Мухаммеда главой мусульман был избран Абу-Бекр с титулом халифа, то есть «наместника». Впоследствии также избирались три халифа: Омар, Осман и Али, но они династии не образовали. Первых четырех преемников Мухаммеда называли «правомерными халифами». Арабо-византийские отношения средневековья во время правления халифа Омара ухудшились из-за вторжения арабов  в византийские пределы.

При жизни Мухаммеда только отдельные отряды бедуинов пересекали византийскую границу. Однако, при втором халифе Омаре события разворачивались довольно быстро. Хронология военных действий 30-40-х годов VII столетия очень запутана и темна. К концу 40-х годов византийская империя была вынуждена навсегда покинуть Египет. После завоевания Египта арабы стали дальше продвигаться на запад по побережью Северной Африки. К 650 году под властью арабов находились Сирия, Верхняя Месопотамия и часть Малой Азии, Палестина,  Египет,  и часть византийских провинций в Северной Африке.

Энергичное сопротивление берберов и междоусобная война между последним халифом Али и сирийским наместником Моавией приостановили дальнейшие завоевания арабов в Северной Африке. В 661 году кровопролитная  война закончилась насильственной смертью Али. После этого престол занял Моавия, основавший династию  Омейядов. Утвердившись во власти, Моавия начал снова воевать с Византией. Он туда послал флот против столицы, и возобновил  продвижение на запад в Северной Африке.

Особенно тяжелые времена пришлись на время правления энергичного императора  Константина IV (668-685 гг.). После прихода арабского флота в Пропонтиду, их базой стал город Кизик. На протяжении нескольких месяцев, обычно в летние месяцы,  арабский флот подступал к Константинополю, и напрасно его осаждал.  Византийские войска успешно отвергали атаку благодаря «греческому огню», который изобрел сирийский грек-перебежчик Каллиник.  Этот огонь отличался одной особенностью, он не горел в воде.

В течение длительного времени этот огонь содействовал успеху византийского флота. После неудавшихся попыток арабских кораблей захватить Константинополь, и после провальных сухопутных военных действий в Малой Азии, Моавия заключил с императором мир при условии уплаты ему определенной ежегодной дани.  Константин  IV,   благодаря  довольно успешному отражению  арабов от Константинополя и заключению с ними почетного и выгодного мира,  оказал большую услугу не только своему государству, но и всей Западной Европе, от которой таким образом удалилась серьезная мусульманская опасность.

При Юстиниане II, преемнике Константина IV, на восточной арабской границе произошло событие, сыгравшее немаловажное значение в арабо-византийских отношениях средневековья. Жители гор сирийского Ливана – мардаиты довольно много хлопот доставляли арабам, но,  в тоже время они были «медной стеной» защищавшей Малую Азию. По просьбе Юстиниана мардаитов переселили во внутренние области империи, и так «разрушили медную стену».