După campanii de succes împotriva sasanizilor și cucerirea ulterioară a Irakului , Khalid și-a stabilit fortăreața în Irak.În timp ce s-a angajat cu forțele sasanide, el s-a confruntat și pe Ghassanids, clienți arabi ai bizantinilor .În curând, Medina a recrutat contingente tribale din toată peninsula Arabică.Tradiția de a ridica armate din contingentele tribale a rămas în uz până în 636, când califul Umar a organizat armata ca departament de stat.Abu Bakr a organizat armata în patru corpuri, fiecare cu propriul comandant și obiectiv.Amr ibn al-A'as: Palestina obiectivă.Deplasați-vă pe traseul Elat, apoi traversați Valea Arabah.Yazid ibn Abu Sufyan: Obiectivul Damasc.Deplasați-vă pe ruta Tabuk.Shurahbil ibn Hasana: Obiectiv Iordania.Deplasați-vă pe ruta Tabuk după Yazid.Abu Ubaidah ibn al-Jarrah: Obiectiv Emesa.Deplasați-vă pe ruta Tabuk după Shurahbil.Neștiind poziția exactă a armatei bizantine, Abu Bakr a ordonat ca toate corpurile să rămână în legătură între ele, astfel încât să poată acorda asistență dacă bizantinii ar putea să-și concentreze armata în orice sector operațional.În cazul în care corpul trebuia să se concentreze pentru o bătălie majoră, Abu Ubaidah a fost numit comandant șef al întregii armate.