הכיבוש של נווה המדבר של תבוכ, אירע, ככל הנראה בשנת 630, על ידי גדודים מוסלמים. הפעולה הצבאית נעשתה בהשראתו של מוחמד, אך ככל הנראה לא תחת פיקודו הישיר. היסטוריונים מוסלמים בני התקופה המצוטטים על ידי אחמד אל-בלאד'רי (أحمد بن يحيى بن جابر البلاذري) שכתב יצירה מונומנטלית, מתארים מסע מלחמה בו השתתפו 30,000 לוחמים מוסלמים. לעומת זאת, לא מוזכר האירוע כלל בכתבים נוצרים וסימני שאלה על נכונותו מרחפים על דיוקו ההיסטורי ואף על עצם קיומו. על פי ההיסטוריוגרפיה המוסלמית, התקדם הצבא המוסלמי לתבוכ אך בנווה המדבר, ששימש כנקודת מפגש לשיירות סוחר, לא חנה צבא ביזנטי וסיורים מוסלמיים נשלחו צפונה אך לא הצליחו להגיע למגע עם כוחות אויב.
כניעת אילת.
תפיסת תבוכ הביאה את הצבא המוסלמי אל סף ארץ ישראל ואת המושלים של תחנות סחר סמוכות לבקש חסות מוסלמית, כך פנה הבישוף של אילה - אל עקבה יוחנה בן רובה אל המרכז החדש בתבוכ שם הציע את כניעת היישוב וקיבל חסות מוסלמית. כך גם נהגו מושלי אדורה ואל ג'רבה. בכתבים מוסלמים נשמרו נוסחי כתבי הנביא למושל אילת:
בכיבוש תבוכ מצוינת נקודת מפנה במדיניות של הנביא מוחמד והאסלאם כלפי היהודים והנוצרים, כאשר לפני כן נקטו המוסלמים בקו אגרסיבי ונוקשה כלפי השבטים היהודים בחצי האי ערב - מדיניות של התאסלמות או השמדה. על גבול ארץ ישראל השתנתה המדיניות המוסלמית, מתוך מחשבה כי כיבוש אזור מאוכלס בצפיפות על ידי יהודים ונוצרים יחייב גישה סבלנית יותר שתמנע התנגדות, והוצע לתושבי הארץ לקבל את המרות המוסלמית ומעמד של ד'ימי (בן חסות) ולשלם מס גולגולת תמורת שמירת הנפש והרכוש.
כיבוש עבר הירדן.
אבו בכר (בערבית: ابو بكر) ירש את מוחמד כמנהיג פוליטי ודתי, והיה לח'ליף הראשון. את שנותיו הראשונות העביר אבו בכר במאמץ להשיב אל חיק האסלאם את השבטים שניצלו את מות הנביא כדי להתנתק מהמסגרת הפוליטית-דתית שיצר. לאחר ביסוס השלטון המוסלמי בחצי האי ערב במלחמות רִדה ("מלחמות הכפירה"), במהלכן השיב אבו בכר אל חיק האסלאם את עשרות השבטים המורדים של חצי האי ערב, התרכז כוח צבאי משמעותי בחצי האי-ערב שהמניע העיקרי לקיומו היה שאיפתם של הלוחמים והמתנדבים במלחמה ששכר שלל וביזה בצידה. לאחר סיום הלחימה בחצי האי הערב נותר כוח זה ללא עיסוק והיווה גורם מסוכן לשלטון המרכזי.
כפתרון לשחרור הלחץ קשר אבו בכר בין האינטרס הבדואי לאינטרס של האסלאם והפנה את תשומת לבו לארץ ישראל. ההיסטוריון הבריטי המילטון א.ר. גיב כתב במחקרו על ההיסטוריה המוסלמית כי הפתרון של הח'ליף למציאות פוליטית-ערבית זו הייתה פתיחה של חזית חדשה, ועבר הירדן המזרחי נבחר גם בגלל הטענה כי מהלך זה הוא למעשה המשך דרכו של הנביא וגם ההבטחה המוקדמת כי שלל המאמינים יהיה רכושם של הביזנטים (נאאם א-רום) המחכה ללוחמים. במהלך שנת 634 יצאו המוסלמים בשני ראשים לכיוון הפרובינציות הביזנטיות של ארץ ישראל.
כוח ראשון בפיקודו של עמר אבן אל-עאץ יצא מהערבה, עבר את אילת ונע לכיוון אזור מישור החוף. כוח מוסלמי שני, שהיה גדול יותר ובו שלושה גדודים נפרדים, אחד בפיקודו של אבו עוביידה בן אל-ג'ראח שני בפיקודו של שרחביל בן חסנה ושלישי בפיקודו של יזיד בן אבו סופיאן, עם בין 3,000 ל-5,000 לוחמים בכל אחד מהגדודים. על פי המסורת המוסלמית (המייחסת את הדברים גם לנביא עצמו) מסר הח'ליף פקודות מפורשות בטרם היציאה לקרב:
הקרב בעמק הציפורים.
הגדוד בפיקודו של יזיד בן אבו סופיאן נתקל בכוח ביזנטי במקום לא מזוהה הקרוי בפי ההיסטוריונים המוסלמים מארג' סופאר ("עמק הציפורים"), הנמצא על פי התיאור המוסלמי "ממזרח לכנרת". מעט מאוד ידוע על העימות והמקורות המוסלמים מוסרים תיאורים סותרים של האירוע. הכוח הביזנטי, ככל הנראה חיל מצב מקומי המורכב בעיקר מבני שבטים הנאמנים לאימפריה בפיקודו של קצין ביזנטי המכונה על ידי המוסלמי "בהאן", הצליח להדוף את המתקפה המוסלמית והסב לכוחות התוקפים אבדות ניכרות שאיימו למוטט את הכוח ולפרק את שורותיו. על פי המסורת המוסלמית ניסו הביזנטים לנצל את מצוקת המוסלמים - שסבלו ככל הנראה גם מרעב - והציעו להם תשלום תמורת נסיגה, הצעה שנדחתה על ידי המוסלמים. לבקשת יזיד בן אבו סופיאן שלח אבו בכר תגבורת של כוחות מתימן שבעזרתם הצליחו המוסלמים להימנע ממפלה מוחלטת והשמדת הכוח המוסלמי. ככל הנראה הצליחה הופעתו של הגדוד המוסלמי לייצב את החזית. תאריך הקרב אף הוא איננו ברור ובעוד מקורות מוסלמים מסוימים קובעים את האירוע לאחר כיבוש פלה ובית שאן, קובע החוקר הישראלי פרופסור משה גיל כי הקרב אכן התרחש במהלך שנת 634. לעומתו קובע ההיסטוריון הבריטי דייוויד ניקול, ככל הנראה תוך מתן פרשנות שונה להיסטוריוגרפיה המוסלמית אך מבלי לפרט את הדיאלקטיקה, כי הקרב נערך בשנת 635, סמוך לכיבוש דמשק וכהקדמה לקרב הירמוך, ונסתיים בתבוסה ביזנטית מוחלטת.
כיבוש מע'אב.
המקורות המוסלמים מציינים את רבת מואב המקראית הידועה גם כמע'אב או אראופוליס (יוונית: Areopolis) - הסמוכה לעיירה ראבה בירדן של זמננו - כמבצר הביזנטי הראשון שנכבש על ידי הצבא המוסלמי, ככל הנראה במהלך שנת 634. מקורות אלו מספרים כי מושל המקום פרווא בן עמר אל-ג'ונדהארני המיר את דתו לאסלאם והוצא להורג על ידי הביזנטים. פעולה קיצונית זאת הביאה את הצבא המוסלמי לפתחה של העיר. המוסלמים חששו כי הביזנטים נאספו בכוח עם תגבורות של שבטים ערבים-נוצרים באזור מבצר מעאן (אראופוליס, Areopolis) בו היה ככל הנראה חיל מצב ביזנטי כמוזכר בכתב היד נוטיטיה דיגניטטום. ריכוז כוחות זה ייתכן ולא כוון כנגד איום ההתפשטות המוסלמי אלא מתוך כוונה להחזיר ולהחיל - לאחר תום הכיבוש הפרסי - את הריבונות הביזנטית על הספר העבר ירדני. דבר אינו ידוע על הצבא הביזנטי והגאוגרף הסורי יאקות אל-חמאווי מזהה את החיילים כ רום (רומאים) אך מספרם ואיכותם לא ידועים. אחמד אל-בלאד'רי מצטט מקור לא ידוע בנוגע לאירועים אך פרטי הקרב אינם נמסרים. הצבא המוסלמי בפיקודו של אבו עוביידה בן אל-ג'ראח יצא מהעימות כאשר ידו על העליונה והמבצר נכבש. המקורות המוסלמים לא מפרטים מה עלה בגורלו של הגדוד הביזנטי. ההיסטוריון הארמני סבאוס מספר על התקפת פתע שהכריעה את הקרב:
כיבוש ארץ ישראל.
העדר אסטרטגיה אחידה ורציפה רדף את האימפריה הביזנטית לאורך כל העימות מול הצבא המוסלמי, למרות מודעות לאיום המתגבש על גבולה, הרשויות הביזנטיות - האזרחיות והצבאיות כאחד לא ציפו לפלישה ולא נערכו לקדם את פני הרעה, הביזנטים נצמדו לקווי פעולה שבלוניים שלא התאימו לעימות המתפתח. אזור הגבול של דרום הפרובינציה פלשתינה עתיד היה להיות זירת קרב אכזרית בין גדודים מוסלמים לחיל המצב הביזנטי. רבות דובר על הלימס פלשתינה, (Limes Palestinae, הגייה מדויקת "לימס פָּלֶסְטִינַיי") - שנועד להגן על האימפריה מפני פלישות של שבטי הנוודים, וכן להבטיח את נתיבי הסחר הבינלאומי החשובים. אך בתקופה הנדונה - המאה ה-7, היה המערך לא יותר ממספר בסיסים לאורך מישור החוף, בעוד שהחלק הפעיל שבו נסתמך על שבטים ערבים שהכירו בשלטון האימפריה הביזנטית.
בראש חיל המצב ביזנטי עמד קצין בשם סרגיוס (ביוונית: Sergios) שנשא בדרגת קנדידטוס (Kandidatos ,κανδιδάτος). סרגיוס הוא, ככל הנראה, אותו קצין המוזכר במקורות אשורים-ארמים במספר גרסאות כ"בירדן" או "ורדן" ששימש גם בממשל הביזנטי בדמשק. היסטוריונים נוצרים ובראשם ניקפורוס הראשון, פטריארך קונסטנטינופול תולים את אי השקט וההתפרצות הערבית במעשיו של סרגיוס שפעל כנגד המסחר הערבי. מקורות אלו טוענים כי סרגיוס, שמתוקף דרגתו הרמה היה בעל גישה לקיסר, שכנע את האחרון למנוע מסחר של הערבים עם ומתוך תחומי האימפריה ולשלול מהם את דמי התווך המסורתי. ניקפורוס מוסיף ומפרט את שרשרת הטעויות של הביזנטים מול ראשי השבטים הערבים ששכנו על גבול האימפריה וראו עצמם בראש וראשונה כמשרתיה. לדבריו אנוך (ביוונית: Ευνούχος) של דמשק עיכב או אף סירב להעביר את התשלומים שנועדו להבטיח את נאמנותם של הערבים, בכך נדחפו שבטים ערבים לצד המוסלמי.
קרב דתין.
ההיסטוריה המוסלמית המסורתית מספרת כי קרב דתין התחולל ב-4 בפברואר 634 בסמוך לעזה, כנראה ליד מעברי נחל בשור בין תל שרוחן לבין תל ג'מה. הגדוד שניסה לחדור לארץ ישראל דרך הנגב בפיקודו של יזיד איבן סופיאן עסק בתקיפה של כפרים ומרכזי יישוב, בין היתר על מנת לקיים את עצמו בהיעדר מערכת אספקה מסודרת. על מנת להדוף את האיום גויס גדוד ביזנטי שמנה לא יותר מ-300 חיילים על ידי מושל קיסריה סרגיוס שנעזר, ככל הנראה, בצי ביזנטי ששט לאורך קו החוף דרומה כדי לתמוך לוגיסטית בכוח היבשתי. מהלך הקרב איננו ברור, אך ככל הנראה בעימות בין הכוחות הלוחמים ניגף הצבא הביזנטי על ידי הגדוד המוסלמי שמנה לפחות 1,000 לוחמים והמפקד הביזנטי נהרג. במקור אשורי לאירועים מסופר על טבח גדול שנערך על ידי הצבא המוסלמי המנצח בכ-4,000 כפריים נוצרים, יהודים ושומרונים. על פי ההיסטוריון דייוויד ניקול, הסתיים הקרב בכישלון מוסלמי שהביא את מפקדי הפלישה המוסלמים לבקש תיגבורת וליזום עימות בשדה קרב עם הצבא הביזנטי שנאסף נגדם בקרב הידוע כקרב אג'נדיין, בו הושמד רוב הצבא הביזנטי שבארץ ישראל.