بلافاصله پس از آن، اعراب به سمت دمشق حرکت کردند و در اوایل اکتبر به آنجا رسیدند. ظاهراً ابوعبیده قبلاً پیام‌رسان خلیفه را دریافت کرده بود و خالد را از عزلش مطلع کرد. بر اساس منابع، خالد بدون اعتراض زیاد آن را پذیرفت، اما این امر جریان گسترش خلافت در منطقه را تغییر داد. ابوعبیده بسیار کندتر و محتاط‌تر از خالد عمل می‌کرد. عمر رویکردی مداخله‌جویانه‌تر نسبت به ارتش داشت و اغلب پس از هر درگیری دستوراتی صادر می‌کرد که به دلیل فاصله تا مدینه، کارزارها را کند می‌کرد. او حتی جاسوسانی در ارتش گماشته بود که باعث شد ابوعبیده در تصمیماتش محتاط‌تر شود. در همین حال، مسلمانان مقداری نیروی کمکی دریافت کردند که تعداد کل نیروهایشان را به ۳۰ هزار نفر رساند.
با این حال، این تنها تغییر در فرماندهی نبود که عمر انجام داد، که ما را به عراق بازمی‌گرداند، جایی که خالد در سال ۶۳۴ مثنی را مسئول ارتش ۹ هزار نفری خود کرده بود. در ماه‌های بعدی، مثنی که تعداد نیروهایش برای فتح زمین‌های بیشتر کافی نبود، تاکتیک یورش‌ها را برای دور نگه داشتن نیروهای برتر ساسانی به کار برد. جزئیات در گذر زمان از بین رفته است، اما ساسانیان که به جنگ‌های منظم عادت داشتند، در مهار این یورش‌ها مشکل داشتند و یکی از آن‌ها حتی به بابل رسید.
بهترین فرمانده ساسانی، رستم، که عملاً دربار شاه ۱۰ ساله یزدگرد را کنترل می‌کرد، تمایلی به ترک پایتخت نداشت و نگران بود که این کار ممکن است شورش دیگری را برانگیزد. اما یورش‌های مثنی بسیار خطرناک بودند، بنابراین این ژنرال تصمیم گرفت فرماندهی نیروها در عراق را بر عهده بگیرد و به سمت جنوب حرکت کند، با پشتیبانی ژنرال‌های ساسانی بهمن، جابان و نرسی، و نجیبزاده ارمنی جالینوس.
حتی قبل از شروع این ضدحمله چندجانبه، مثنی می‌دانست که به نیروی کمکی نیاز دارد و پیام‌رسانی به پایتخت فرستاد. تا اوت این پیام‌رسان به مدینه رسید، درست در زمان به قدرت رسیدن عمر. خلیفه جدید ابوعبید (نه ابوعبیده) را به فرماندهی در عراق منصوب کرد و حدود ۶ هزار نیرو به او داد تا مثنی را تقویت کند. مثنی اکنون از ضدحمله ساسانیان مطلع شده بود و وقتی جابان در اواخر سپتامبر به حیره نزدیک شد، فرمانده عرب آنجا را رها کرد و به خفان عقب‌نشینی کرد. تا اوایل اکتبر ابوعبید به او پیوست و تعداد کل نیروهای خلافت به بیش از ۱۵ هزار نفر رسید، تقریباً برابر با نیروهای تحت فرماندهی جابان که از فرات عبور کرده بود و اکنون در نماریق بود. جزئیات نبرد نماریق مشخص نیست، اما به نظر می‌رسد جابان شکست کوچکی متحمل شد و مجبور به عقب‌نشینی به آن سوی رودخانه شد.
ابوعبید تصمیم گرفت با ارتش‌های در حال نزدیک شدن ساسانی جداگانه بجنگد و به سمت شمال به طرف کسکر حرکت کرد، با این امید که ارتش کوچک‌تر تحت فرماندهی نرسی را شکست دهد و او را از میدان به در کند. اگرچه مسلمانان دوباره پیروز شدند، ارتش پارسی عمدتاً سالم عقب‌نشینی کرد و ابوعبید که می‌دانست جالینوس ممکن است راه عقب‌نشینی به حیره را قطع کند، با سرعت دو برابر ارتشش را حرکت داد تا از این اتفاق جلوگیری کند. در واقع، ارتش خلافت قبل از اینکه جالینوس آن‌ها را مسدود کند، به شهر رسید. نزدیک‌ترین ارتش‌های ساسانی به حیره، نیروهای جالینوس و بهمن بودند. نامه‌ای از رستم به آن‌ها دستور داد نیروهایشان را متحد کنند، از فرات عبور کنند و به شهر حمله کنند.
در اواخر اکتبر ۶۳۴، ارتش‌های متحد آن‌ها با حدود ۲۰ هزار نفر سعی کردند از رودخانه نزدیک کوفه عبور کنند، اما ابوعبید و ۱۵ هزار نفرش توانستند از این گذر جلوگیری کنند. برای مدتی، ارتش‌ها در مقابل یکدیگر ایستادند و به یکدیگر ناسزا می‌گفتند، تا اینکه یک فرستاده ساسانی با پیام بهمن به ابوعبید نزدیک شد: "یا شما به سمت ما عبور کنید، و ما اجازه خواهیم داد، یا ما به سمت شما عبور خواهیم کرد، و شما باید اجازه دهید!"
اگرچه افسرانش اعتراض کردند، ابوعبید مشتاق بود عبور کند و در یک نبرد منظم بجنگد، بنابراین به ارتشش دستور داد این کار را انجام دهد. با دیدن این صحنه، بهمن نیروهایش را کمی به سمت شمال جابجا کرد و به مسلمانان اجازه داد عبور کنند و صف‌آرایی کنند. برخلاف نبردهای قبلی، پارسی‌ها حدود یک دوجین فیل داشتند که در پیشقراول قرار داده شده بودند با سواره‌نظام سنگین بین آن‌ها و پیاده‌نظام در رده دوم. ارتش ابوعبید در عرض ۲ ساعت از رودخانه عبور کرد و شروع به صف‌آرایی کرد، دوباره با سواره‌نظام در جلو و پیاده‌نظام در خط دوم. بهمن همچنان منتظر ماند و این ابوعبید بود که به سربازانش دستور حمله داد.
سواره‌نظام عرب به جلو تاخت، اما اسب‌هایشان از فیل‌ها می‌ترسیدند، احتمالاً برای اولین بار آن‌ها را می‌دیدند، و حمله قبل از رسیدن به خطوط ساسانی متوقف شد. در پاسخ، بهمن تیراندازانش را به جلو فرستاد و به آن‌ها دستور داد به اعراب در حال عقب‌نشینی شلیک کنند. این شلیک‌ها بسیاری را کشت یا زخمی کرد، و وقتی رهبران ارتش خلافت سعی کردند تیراندازانشان را به جلو بفرستند تا درگیری شروع شود، کل خط عرب آشفته و از هم گسسته شد.
فرمانده پارسی از این فرصت استفاده کرد و سواره‌نظام و فیل‌هایش را به حمله فرستاد. در حالی که سواره‌نظام عمدتاً متوقف شد، فیل‌ها به راحتی در هر نقطه‌ای که ضربه زدند، شکاف ایجاد کردند. ارتش عرب به آرامی، اما مطمئناً به عقب رانده شد. حضور فیل‌ها اسب‌ها را وحشت‌زده کرده بود، بنابراین برای تثبیت جبهه، ابوعبید به سوارانش دستور داد از اسب پیاده شوند. او خود گروهی از جنگجویان را رهبری کرد و چند فیل و همراهانشان را کشت. با این حال، فیل دیگری به سمت رهبر عرب فرستاده شد و به زودی او توسط این حیوان کشته شد.
بسیاری از رهبران دیگر مسلمان کشته شدند و ارتششان شروع به فرار آشفت‌آمیز کرد، و ساسانیان شروع به تعقیب آن‌ها کردند. مثنی یکی از آخرین فرماندهان باقی‌مانده بود و توانست تا حدی انضباط و سازماندهی در محل گذرگاه ایجاد کند، با رهبری نیروی پشتیبانی و اجازه دادن به باقی‌مانده ارتش برای عقب‌نشینی. او در این نبرد به شدت زخمی شد، اما اقداماتش هزاران نفر را نجات داد. نبرد پل اولین نبردی بود که پارسی‌ها در این جنگ پیروز شدند. بیش از ۱۰ هزار مسلمان کشته شدند، در حالی که تلفات ساسانیان حدود ۲ هزار نفر بود.
در هفته‌های بعد، بهمن مثنی را که به الیس عقب‌نشینی کرده بود، تعقیب نکرد و به تیسفون بازگشت. برخی منابع ادعا می‌کنند که شورش دیگری علیه رستم رخ داد، برخی دیگر می‌گویند بهمن برای مقابله با مهاجمان ترک فرستاده شد. منابع همچنین در مورد رویدادهای بعدی در عراق در سال ۶۳۴ و سپس در سال ۶۳۵ اختلاف نظر دارند، برخی از وقایع‌نگاران ادعا می‌کنند که ارتش مثنی فرار کرد و او تمام فتوحات قبلی را رها کرد، و برخی دیگر می‌گویند که ساسانیان ارتش بزرگی تحت فرماندهی میهران فرستادند و این ارتش در آوریل ۶۳۵ در بویب به طور قطعی شکست خورد. در هر صورت، این وقفه در عملیات به ما اجازه می‌دهد به شام بازگردیم.
ارتش مسلمان به ساختار فرماندهی جدید عادت می‌کرد، و با استفاده از این وقفه، هراکلیوس نیروهای بیشتری را به منطقه می‌آورد، از طریق زمینی به انطاکیه و از طریق دریایی به بنادر مختلف، زیرا رومی‌ها کنترل کامل دریایی داشتند. گروه دوم تحت فرماندهی تئودور تریتیریوس، خزانه‌دار امپراتوری قرار داشت و در دسامبر ۶۳۴ شروع به تجمع در غرب پلا کرد، که مکان مناسبی برای راه‌اندازی یک حمله شرقی بود و خط ارتباطی با عربستان را قطع می‌کرد. مشخص نیست که این ارتش چقدر بزرگ بود. جاسوسان ابوعبیده را در دسامبر از این تهدید مطلع کرده بودند و در اوایل ژانویه ۶۳۵ او به سمت جنوب به طرف پلا حرکت کرد و یک سپاه تحت فرماندهی یزید را در پشت سر گذاشت.
به محض اینکه پادگان کوچک پلا از این موضوع مطلع شد، به سمت ارتش اصلی عقب‌نشینی کرد، رودخانه اردن را طغیان داد و منطقه‌ای شبیه به مرداب ایجاد کرد که ارتش‌های بیزانس و عرب را از هم جدا می‌کرد. پس از اشغال پلا، فرماندهان ارتش عرب تصمیم گرفتند به سمت بیت‌شان حرکت کنند تا با تئودور درگیر شوند. آن‌ها با زمین این منطقه آشنا نبودند، بنابراین به زودی پیشقراول تحت فرماندهی خالد در گل‌ولای گیر کرد و مسلمانان مجبور به عقب‌نشینی به پلا شدند.
تئودور حدود یک هفته منتظر ماند، با این امید که دشمنانش کمتر هوشیار شوند. در ۲۳ ژانویه، نیروهایش را به سمت رودخانه حرکت داد با طرحی برای حمله به اردوگاه مسلمانان در شب. با این حال، مسلمانان نیروهای پیشقراولی را در امتداد رودخانه مستقر کرده بودند، بنابراین به محض اینکه رومی‌ها شروع به عبور کردند، اردوگاه عرب مطلع شد و شروع به آماده شدن برای نبرد کرد.
ما فقط جزئیات محدودی از این نبرد داریم که بر اساس منابع عربی، در طول شب و بیشتر روز بعد ادامه یافت. رومی‌ها با استفاده از تعداد کمی بیشتر نیروهایشان، حریفان را به سمت اردوگاه به عقب راندند. بر اساس یک وقایع‌نامه، تئودور در یکی از حملات زخمی شد و از دست دادن روحیه ناشی از آن باعث عقب‌نشینی رومی‌ها شد. وقتی آن‌ها شروع به عبور از یک مرداب کردند، اعراب از این فرصت استفاده کردند: حمله کردند و هزاران نفر را کشتند. بقیه به بیت‌شان بازگشتند.
هرچه از ارتش روم باقی مانده بود، در پادگان‌های مختلف در غرب و جنوب پراکنده شد، در حالی که تئودور از طریق دریا به انطاکیه بازگشت. هیچ ارتشی برای مقابله با ابوعبیده باقی نمانده بود، بنابراین او ارتشش را به سپاه‌هایی تقسیم کرد تا تا حد امکان شهرها را فتح کند. شرحبیل بیت‌شان و سپس طبریه را گرفت. پس از آن شرحبیل و عمرو بن عاص به سمت جنوب رفتند، در حالی که ابوعبیده و خالد به سمت شمال حرکت کردند. تا مارس ۶۳۵ مسلمانان کنترل کل منطقه جنوب بیروت را در دست داشتند، به جز قیصریه، که در برابر محاصره تقویت‌شده توسط هراکلیوس مقاومت کرد، و اورشلیم، که استحکامات قوی‌ترین را داشت.
احتمالاً هراکلیوس فکر می‌کرد مسلمانان با محاصره‌ها مشغول خواهند بود و او فرصتی دارد، بنابراین مشغول بسیج نیرو برای ضدحمله در سال ۶۳۶ بود. همزمان، اتحاد با یزدگرد برقرار شد و هراکلیوس نوه‌اش را به ازدواج شاه جوان ساسانی در آورد. برنامه این بود که پارسیان مواضع مسلمانان را از شرق مورد حمله قرار دهند. در همین حال، ۱۵ هزار نفر ابوعبیده به سمت شمال حرکت کردند و تا نوامبر منطقه بین دمشق و حمص را تصرف کردند و این شهر مهم را در معرض خطر قرار دادند. هراکلیوس به سرعت نیروهای کمکی فرستاد که تعداد نیروهای تحت فرماندهی فرمانده پادگان حارث به ۸ هزار نفر رسید. در اوایل دسامبر شهر تحت محاصره قرار گرفت.
رومیان امیدوار بودند که اعراب که به سرما عادت ندارند، نتوانند محاصره را برای مدت طولانی تحمل کنند. از طرف دیگر، حمص شهری مستحکم بود با دیوارهایی به قطر ۱ مایل و خندقی که آن را احاطه کرده بود و یک ارگ درون دیوارها، بنابراین وضعیت مدافعان ناامیدکننده نبود. مسلمانان در آن زمان در هنر محاصره مهارت چندانی نداشتند و کمبود ادوات محاصره، حمله را غیرممکن می‌ساخت. بنابراین، برای هفته‌ها و سپس ماه‌ها طرفین جز تیراندازی کاری نکردند.
مارس ۶۳۶ زمستان رو به پایان بود و مشخص شد که ارتش عرب قصد دارد حمصی‌ها را با گرسنگی تسلیم کند. ذخایر غذایی به طور خطرناکی کاهش یافته بود، بنابراین حارث تصمیم گرفت حمله کند و تا حد ممکن دشمن را بکشد، با این باور که این کار ممکن است محاصره را پایان دهد. او واحدهای کوچکی برای دفاع از دیوارها باقی گذاشت و بیش از ۵ هزار نفر را نزدیک دروازه جنوبی متمرکز کرد. در ابتدا این حمله بسیار موفق بود - مسلمانان غافلگیر شده بودند و نسبت نیروها ۲ به ۱ به ضررشان بود که منجر به صدها تلفات شد و آن‌ها را مجبور به عقب‌نشینی تحت فشار حارث کرد. با این حال، خالد موفق شد سواره‌نظام خود را جمع کند و اندکی پس از آن به منطقه نبرد رسید. اکنون تعداد نیروها به نفع اعراب بود و این برای رومی‌ها کافی بود تا جنگ را قطع کنند و به پناهگاه دیوارها بازگردند.
مدافعان خوشحال بودند و اصلاً تعجب نکردند وقتی ارتش مسلمان در جنوب جمع شد و شروع به عقب‌نشینی کرد. حارث تصمیم گرفت که می‌تواند پیروزی درخشانی به دست آورد و بلافاصله با همان ۵ هزار نفر از شهر خارج شد. او چند مایل جنوبی‌تر به مسلمانان در حال عقب‌نشینی رسید، اما به محض اینکه سواره‌نظام او شروع به حمله کرد، واحدهای ابوعبیده برگشتند و حمله کردند. چند دقیقه بعد رومی‌ها از همه طرف محاصره شدند. حارث کشته شد و فقط چند صد نفر از سربازانش فرار کردند. پس از نبرد کوتاه، اعراب به شهر بازگشتند و پادگان که بدون رهبر مانده بود تسلیم شد.
در همین حال، در شمال، امپراتور هراکلیوس مدتی بود که در حال آماده‌سازی ارتشی برای ضدحمله بود. منابع مختلف تعداد این ارتش را از ۳۰ هزار نفر واقع گرایانه تری تا ۴۰۰ هزار نفر خیالی ذکر کرده‌اند. باید توجه داشت که وقایع‌نگارانی که درباره این جنگ نوشته‌اند حداقل یک یا دو نسل پس از وقایع می‌زیسته‌اند، بنابراین توصیفات آن‌ها بر اساس مشاهدات دست اول یا حتی دست دوم نبوده است. ما می‌دانیم که در اوج جنگ بیزانس-ساسانی ۶۰۲-۶۲۸، هراکلیوس توانست ارتشی ۷۰ هزار نفری برای حمله به امپراتوری ساسانی بسیج کند، اما این ارتش عنصر قابل توجهی از گوکترک‌ها را داشت. در عین حال، بیزانسی‌ها مجبور بودند برخی نیروها را در ایتالیا، بالکان و قفقاز نگه دارند تا از پیشروی لومباردها، اسلاوها، آوارها و خزرها جلوگیری کنند. به نظر ما، بیزانسی‌ها حداقل ۲ به ۱ از حریفان خود بیشتر بودند، اما با توجه به وضعیت لجستیکی در منطقه عملیات، تعدادشان کمتر از ۱۰۰ هزار نفر بود.
هراکلیوس که اکنون در دهه ۶۰ زندگی‌اش بود، از بیماری اِدِم یا خیز رنج می‌برد، بنابراین قصد نداشت شخصاً ارتش متشکل از یونانی‌ها، ارمنی‌ها و عرب‌های مسیحی را رهبری کند. در عوض، ارتش به ۵ ستون تقسیم شد که توسط ۵ ژنرال فرماندهی می‌شدند. برنامه این بود که نیروهای مسلمان را در اطراف حمص درگیر و محاصره کنند و از ستون دیگر برای تصرف دمشق استفاده کنند و مانع از تقویت گروه شمالی توسط نیروهای خلافت در جنوب شوند.
ارتش در اواسط ژوئن از انطاکیه خارج شد. متأسفانه برای رومی‌ها، چند روز قبل از رسیدن ستون پیشرو به حمص، اعراب از ضدحمله مطلع شدند، یا از طریق جاسوسان خود یا از اسرایی که در حمله به شیزر گرفته بودند، بنابراین ابوعبیده به سپاه خود دستور عقب‌نشینی داد. در ابتدا، ایده این بود که به دمشق عقب‌نشینی کنند تا این فتح را حفظ کنند، اما شهر توسط فضای باز احاطه شده بود که به ارتش با تعداد برتر مزیت می‌داد، بنابراین اعراب شروع به عقب‌نشینی به سمت جابیه کردند که بین رودخانه یرموک در جنوب، دریاچه طبریه در غرب و صحرا در شرق قرار داشت. پیام‌رسان‌ها به گروه جنوبی فرستاده شدند تا به سمت جابیه حرکت کنند.
بیزانسی‌ها که به سختی فرصت نابودی حریف در اطراف حمص را از دست داده بودند، شروع به تعقیب اعراب کردند و پس از تصرف شهر به تدریج تجمع کردند. آن‌ها دمشق را بازپس گرفتند و به سمت جنوب ادامه دادند و گاهی در اواسط ژوئیه ۶۳۶، پیشقراولان آن‌ها با نیروی پشتیبانی خلافت در شمال جابیه تماس برقرار کردند.
فرماندهان عرب که در ابتدا از موقعیت خود راضی بودند، اکنون فهمیدند که ممکن است از جنوب غرب مورد حمله قرار گیرند - از طریق گذرگاه باریک بین دریاچه طبریه و رودخانه یرموک. ارتش صحرایی بیزانس می‌توانست از جلو به آن‌ها حمله کند، در حالی که پادگان قیصریه می‌توانست از گذرگاه استفاده کند. بنابراین، ابوعبیده خالد را به فرماندهی نیروی پشتیبانی گذاشت و شروع به جابجایی نیروهایش کرد. خالد با پیشقراولان بیزانس درگیر شد که توسط سواره‌نظام سبک عرب مسیحی رهبری می‌شد و به بقیه ارتش اجازه داد بدون مزاحمت حرکت کنند.
