پس از لشکرکشی‌های موفقیت‌آمیز علیه ساسانیان و متعاقب آن فتح عراق ، خالد سنگر خود را در عراق ایجاد کرد.در حالی که با نیروهای ساسانی درگیر بود، با غسانیان، مشتریان عرب بیزانس نیز مقابله کرد.مدینه به زودی نیروهای قبیله ای را از سراسر شبه جزیره عربستان به خدمت گرفت.سنت تشکیل ارتش از قبایل تا سال 636، زمانی که خلیفه عمر ارتش را به عنوان یک اداره دولتی سازماندهی کرد، همچنان مورد استفاده قرار گرفت.ابوبکر لشکر را به چهار سپاه که هر یک فرمانده و هدف خاص خود را داشت، سازماندهی کرد.عمرو بن العاص: فلسطین عینی.در مسیر الات حرکت کنید، سپس از دره عربا عبور کنید.یزید بن ابوسفیان: عین دمشق.در مسیر تبوک حرکت کنید.شورهبیل بن حسنه: عین اردن.بعد از یزید در مسیر تبوک حرکت کنید.ابوعبیده بن الجراح: عمسه عینی.بعد از شورهبیل در مسیر تبوک حرکت کنید.ابوبکر که موقعیت دقیق ارتش بیزانس را نمی دانست، دستور داد که همه سپاه ها با یکدیگر در ارتباط باشند تا اگر بیزانسی ها می توانستند ارتش خود را در هر بخش عملیاتی متمرکز کنند، بتوانند کمک کنند.در صورتی که سپاه مجبور بود برای یک نبرد بزرگ متمرکز شود، ابوعبیده به فرماندهی کل ارتش منصوب شد.