Преследуя отступавший отряд Халида-ибн-Саида, ромеи изгнали его из пределов Заиорданья. Опасаясь того, что разбившие Ибн-Саида ромейские войска, обогнув Мертвое море с юга, зайдут ему в тыл, Язид отступил из Южной Палестины в ал-Балка. Вскоре Абу-Бекр, убедившись в непригодности Халида-ибн-Саида как полководца, отстранил его от командования, назначив Язида вести военные действия в Заиорданье. На место же Язида в Южную Палестину был послан отряд под командой Амра-ибн-ал-Аса. В Заиорданье арабам пришлось столкнуться с упорным сопротивлением ромейских войск, общее командование над которыми принял брат Ираклия Феодор. Поэтому, не полагаясь на одного Язида, халиф вскоре отправил туда отряды под командой Шурахбиля-ибн-Хасаны и Абу-Убейды-ибн-ал-Джарраха.
Затем было принято решение объединить все отряды под единым командованием. Верховным главнокомандующим был назначен Халид-ибн-ал-Валид, считавшийся у арабов самым лучшим полководцем. В свое время именно он сумел после гибели военачальников в сражении при Муте спасти в результате умелого отступления остатки арабского отряда от истребления. В других битвах арабы под его командованием, как правило, одерживали победы. Мухаммед дал ему прозвище Меч Аллаха. Халиф Абу-Бекр послал Халида на войну с персами, и к тому моменту, когда первый принял решение перевести его на византийский театр военных действий, последний находился в земле подчиненных Сасанидам лахмидов. Получив приказ халифа, Халид оставил воевать с персидскими войсками полководца Мусанну-ибн-Харису, а сам с отрядом воинов выступил в Сирию. Численность его отряда не установлена.
После перехода по пустыне Халид внезапно появился в окрестностях Дамаска и, напав на гассанидов, разгромил их при Мардж-Рахите 24 апреля или 12 июня 634 г.
Еще до прибытия Халида в Сирию арабы заставили капитулировать Мааб и осадили Бостру. Сюда после битвы при Мардж-Рахите и подошел Халид. Соединившись с другими вождями, он дал ромеям бой под стенами Бостры и, нанеся им поражение, принудил город к капитуляции.
К тому времени все ромейские войска на востоке были подчинены брату Ираклия Феодору. Большая их часть заняла позиции на реке Ярмуке, левом притоке Иордана, преграждая арабам путь на север; меньшая двинулась в Палестину против Амра. Войска на Ярмуке возглавил сам Феодор, в Палестине – полководец, которого сирийская хроника 1234 г. называет Киклаос. Армия Киклаоса встретилась с войсками Амра-ибн-ал-Аса при Аджнадине к юго-западу от Иерусалима. Здесь, согласно большинству арабских источников, 30 июля 634 г. произошла битва, в которой ромеи были наголову разгромлены.
Битва при Аджнадине окончательно поставила Южную Палестину под контроль арабов и создала условия как для дальнейшего их продвижения к северу, так и для завоевания Синая. Уже в сентябре 634 г. они контролировали все пути от Аскалона к Синаю, а к концу того же года – от Иерусалима к осажденному ими Вифлеему. Такому успеху мусульман в немалой степени способствовали перешедшие на их сторону византийские арабы, хорошо знавшие страну и служившие проводниками. Впрочем, как мы указывали выше, не все ромейские арабы занимали одинаковую позицию. Некоторые из них до конца сохранили верность византийцам, другие меняли свою ориентацию в зависимости от обстоятельств. Так, арабы-христиане, жившие на Синайском полуострове, укрепились в горной местности и длительное время оказывали мусульманам сопротивление. Затем, убедившись в превосходстве врага, они приняли ислам и присоединились к завоевателям.
Способствовала успехам арабов также позиция иудейского населения Византии, встречавшего их как освободителей. Дело в том, что евреи, в течение веков испытывавшие в Византийской империи национальный гнет, во время кризиса, разразившегося в конце VI – начале VII вв., усилили освободительную борьбу. Во время войны Византии с Персией они переходили на сторону персов, когда же последние потерпели поражение, обратили свои взоры в сторону Аравии. После того как там было создано мусульманское государство, среди части иудеев распространилось мнение, что Мухаммед и есть ожидаемый ими Мессия. Этому способствовало, вероятно, некоторое сходство религиозных предписаний ислама и иудаизма (неупотребление в пищу свинины, запрещение священных изображений и т. д.). Кроме того, согласно Библии, евреи и северные арабы произошли от одного предка Авраама (ар. Ибрахим). Таким образом, иудеи могли рассматривать арабов как своих «родственников». Впрочем, вскоре завоеватели своими грабежами и убийствами мирного населения, во время которых не различали иудеев от христиан, несколько умерили их восторг, однако в целом иудеи продолжали относиться к арабам благожелательнее, нежели к ромеям.
При всех благоприятных факторах минусом арабского войска являлось неумение на первых порах штурмовать города. Именно это надолго задержало полное завоевание сиро-палестинского региона. Многие города (Газа, Кесария Приморская и др.) выдерживали осаду в течение многих месяцев и даже нескольких лет.