After successful campaigns against the Sassanids and the ensuing conquest of Iraq, Khalid established his stronghold in Iraq. While engaged with Sassanid forces, he also confronted the Ghassanids, Arab clients of the Byzantines. Medina soon recruited tribal contingents from all over the Arabian peninsula. The tradition of raising armies from tribal contingents remained in use until 636, when Caliph Umar organised the army as a state department. Abu Bakr organised the army into four corps, each with its own commander and objective.

• Amr ibn al-A'as: Objective Palestine. Move on Elat route, then across Valley of Arabah.
• Yazid ibn Abu Sufyan: Objective Damascus. Move on Tabuk route.
• Shurahbil ibn Hasana: Objective Jordan. Move on Tabuk route after Yazid.
• Abu Ubaidah ibn al-Jarrah: Objective Emesa. Move on Tabuk route after Shurahbil.

Not knowing the precise position of the Byzantine army, Abu Bakr ordered that all corps should remain in touch with each other so that they could render assistance if the Byzantines were able to concentrate their army in any operational sector. In case the corps had to concentrate for one major battle, Abu Ubaidah was appointed Commander-in-Chief of the entire army.