Após campanhas bem-sucedidas contra os sassânidas e a subsequente conquista do Iraque , Khalid estabeleceu sua fortaleza no Iraque.Enquanto esteve envolvido com as forças sassânidas, também confrontou os gassânidas, clientes árabes dos bizantinos .Medina logo recrutou contingentes tribais de toda a Península Arábica.A tradição de formar exércitos a partir de contingentes tribais permaneceu em uso até 636, quando o califa Umar organizou o exército como um departamento de estado.Abu Bakr organizou o exército em quatro corpos, cada um com seu comandante e objetivo.Amr ibn al-A'as: Palestina Objetiva.Siga pela rota Elat e depois atravesse o Vale de Arabah.Yazid ibn Abu Sufyan: Objetivo Damasco.Siga a rota Tabuk.Shurahbil ibn Hasana: Objetivo Jordânia.Siga pela rota Tabuk depois de Yazid.Abu Ubaidah ibn al-Jarrah: Objetivo Emesa.Siga na rota Tabuk depois de Shurahbil.Desconhecendo a posição precisa do exército bizantino, Abu Bakr ordenou que todos os corpos permanecessem em contacto uns com os outros para que pudessem prestar assistência caso os bizantinos conseguissem concentrar o seu exército em qualquer sector operacional.Caso o corpo tivesse que se concentrar em uma grande batalha, Abu Ubaidah foi nomeado comandante-chefe de todo o exército.