Sasanilere karşı başarılı kampanyalar ve ardından gelen Irak'ın fethinden sonra Halid, Irak'ta kalesini kurdu.Sasani güçleriyle çatışma halindeyken aynı zamanda Bizans'ın Arap yandaşları olan Ghassanidlerle de karşı karşıya geldi.Medine çok geçmeden Arap yarımadasının her yerinden kabile birliklerini topladı.Kabile birliklerinden ordu kurma geleneği, Halife Ömer'in orduyu bir devlet dairesi olarak örgütlediği 636 yılına kadar kullanımda kaldı.Ebu Bekir orduyu her birinin kendi komutanı ve hedefi olan dört kolordu halinde organize etti.Amr ibn al-A'as: Objektif Filistin.Elat rotası boyunca ilerleyin, ardından Arabah Vadisi boyunca ilerleyin.Yezid ibn Ebu Süfyan: Hedef Şam.Tebük güzergahında hareket edin.Shurahbil ibn Hasana: Objektif Ürdün.Yezid'den sonra Tebük güzergahına doğru hareket edin.Abu Ubaidah ibn al-Jarrah: Objektif Emesa.Şurahbil'den sonra Tebük güzergahına doğru hareket edin.Bizans ordusunun kesin konumunu bilmeyen Ebu Bekir, Bizanslıların ordularını herhangi bir operasyonel bölgede yoğunlaştırabilmeleri durumunda yardım sağlayabilmeleri için tüm birliklerin birbirleriyle iletişim halinde kalmasını emretti.Kolordu büyük bir savaşa konsantre olmak zorunda kalırsa, Ebu Ubeyde tüm ordunun Başkomutanı olarak atandı.