The Emperor Heraclius, having received intelligence of the movements of the Muslim armies from his Arab clients, began to plan countermeasures. Upon Heraclius' orders, Byzantine forces from different garrisons in the north started moving to gather at Ayjnadyn.

Abu Ubaidah informed the Caliph about the preparations made by the Byzantines in the third week of May 634. Because Abu Ubaida didn't have experience as a commander of military forces in such major operations, especially against the powerful Roman Army, Abu Bakr decided to send Khalid ibn Walid to assume command.

Khalid immediately set out for Syria from Al-Hirah, in Iraq, in early June, taking with him half his army, about 8000 strong. Khalid selected a shorter route to Syria, an unconventional route passing through the Syrian Desert. It is recorded that his soldiers marched for two days without a single drop of water, before reaching a predetermined water source at an oasis. Khalid thus entered Northern Syria and caught the Byzantines on their right flank. According to modern historians, this ingenious strategic maneuver unhinged the Byzantine defences in Syria.