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

Другое назначение, имевшее долговременные последствия, — это назначение Амр ибн аль-Аса, отличавшегося скорее проницательностью и коварством, чем воинскими доблестями, хитроумного Одиссея первых исламских армий. В прошлом купец из Газы, он был избран Пророком для сбора податей с племен на пути от Медины к Сирии. Он предпочел увести своих людей, числом якобы около трех тысяч, среди которых многие были из Мекки и из Медины, в места, которые хорошо изучил ранее. Он дошел вдоль побережья Красного моря до самого залива Акаба, откуда повернул на запад и обосновался со своими людьми в огромной пустынной долине Вади Араба между Иорданом и Израилем. Оттуда они поднялись по крутизне на плато Негев и направились к приморской Газе. Там Амр начал переговоры с командующим местным ополчением, возможно, требуя от него денег, и, согласно преданию, византийский наместник пытался захватить или убить его во время переговоров. Наконец, 4 февраля 634 года произошло сражение, в котором Амр и его люди одержали верх над маленьким византийским войском у селения Датхин под Газой и убили византийского командующего. Победа арабов произвела впечатление. Весть о ней распространилась быстро, и говорили, что иудейское поселение под Кесарией открыто ликовало, радуясь смерти византийского офицера и унижению имперской власти.

Победа мусульман у Датхина, пусть и не слишком масштабная, насторожила византийские власти, предупредив их о новой угрозе с юга. Верховным главнокомандующим был император Ираклий. Ему к тому времени было около 60 лет, и он нисколько не походил на изнеженных обитателей роскошных константинопольских дворцов: этот человек обладал огромным военным опытом и был привычен к трудностям военных кампаний. Кроме того, он находился на вершине власти и ко времени начала мусульманских операций против Сирии как раз отметил свой главный триумф — возвращение в Иерусалим животворящего Креста Господня. Ираклий ни разу лично не возглавлял войско (как и мусульманские халифы никогда не возглавляли армии ислама), но он оставался в тылу сирийских войск, в Хомсе или Антиохии, направляя их действия, назначая генералов и отдавая распоряжения. Интересно отметить, как изображают Ираклия арабские источники. Они отдают должное остроте его ума, мудрости и умению предвидеть будущее. В одном рассказе знатный мекканец Абу Суфйан говорит, что видел Ираклия, когда тот с купцами посещал Сирию:

Рассказ изображает его победоносным, но скромным и благочестивым.

Во множестве рассказов Ираклию приписывают признание величия Мухаммада и готовность перейти в мусульманство, если бы не враждебность к исламу византийской знати. Для арабов он был ключевой фигурой, символом византийского сопротивления армиям ислама, исконным врагом. Его изображают гордым и самовластным, но упоминают и моменты, когда он один из своих советников и придворных сознавал силу мусульман и предвидел их победу. Арабские источники рисуют Ираклия без особой враждебности: он —трагическая фигура, человек, потерпевший поражение и окончивший жизнь в унижении из-за невозможности перейти в ислам.

До этого времени атаки мусульман на Сирию представляли собой мелкие приграничные вылазки. Следующая стадия завоевания начинается прибытием Халида ибн аль-Валида и его людей, которые форсированным маршем пересекли пустыню от Ирака, на окраинах которой они сражались. Марш Халида через Сирийскую пустыню с полусотней воинов отмечен в истории и овеян легендами. Арабские источники дивятся его стойкости; современные ученые восхищаются мастерским стратегическим ходом. Часто рассказывают, как он совершил шестидневный переход по безводной пустыне, заставив своих верблюдов напиться до отвала и завязав им морды, чтобы они не могли жевать жвачку, а затем убивая их одного за другим, чтобы люди могли напиться воды из их желудков. В другой раз, когда его люди изнемогали от жажды, он спросил одного из своих воинов, Рафи, бывавшего прежде в тех местах, не знает ли тот, где найти воду. Рафи ответил, что вода рядом: «Иди вперед, пока не увидишь два пригорка, подобных грудям женщины, и тогда иди к ним». Когда они добрались до пригорков. Рафи велел искать терновый куст, похожий на ягодицы мужчины. Они обыскали все, и нашли корни, но ни одного куста, однако Рафи сказал, что это то самое место, и приказал копать. Скоро они дошли до слоя влажной земли и добыли немного отличной воды. Тогда Рафи с великим облегчением сказал Халиду: «О, начальник, я не был у этого источника более тридцати лет. Я видел его лишь однажды, когда был здесь в детстве с отцом». Так, продолжает рассказчик, они подготовились и атаковали врагов, не подозревавших, что враг может обрушиться на них из пустыни.

Беда в том, что описания этой экспедиции хотя и живописны, но очень запутанны. Мы можем не сомневаться, что Халид перешел пустыню от Ирака до Сирии весной или в начале лета 634 года, что это достопамятный подвиг стойкости его воинов и что его появление в Сирии сыграло важную роль в успехах мусульманского оружия. Трудность состоит в том, что одни источники описывают его путь по более длинному южному маршруту через Думат аль-Джандал, а другие столь же уверенно — путь через лежащую к северу Пальмиру. Обе стороны приводят веские аргументы, и какая версия верна, попросту неизвестно.

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