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