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