Huhut siitä, että bysanttilaiset varustivat armeijaa hyökätäkseen Yathribiin, saivat alkunsa Petran alueelta tulleiden nabatealaisten kauppiaiden kertomuksista. He olivat saapuneet kaupunkiin sillä aikaa, kun Muhammad piileskeli vaimoiltaan majassaan. Vaikka se oli vain huhua, aiheutti se kuitenkin pelkoa. Bysanttilaiset ja heidän arabikristityt liittolaisensa olivat sen ajan mahtavin valtakunta. Herakleios oli vasta hiljattain kukistanut persialaiset ja oli nyt vapaa hyökkäämään uutta profeettaa vastaan, tai näin ainakin puhuttiin Yathribissa. Huhut saivat vauhtia ja kerrottiin, että Herakleios oli maksanut joukoilleen vuoden palkan etukäteen varautuessaan sotaretkeen. Ja mikä pahinta, Ghassanidit, Judhamisit, Lakhamidit ja muut kristityt arabit "parveilivat Rooman kotkien ympärillä ja etuvartio oli jo Balqassa" lähellä Mutaa, missä Jabir, Rawaha ja Zaid kohtasivat kohtalonsa vuotta aikaisemmin.
Tultuaan alas majastaan Muhammad ei tuhlannut aikaa kootessaan armeijan, joka oli suurempi kuin mikään hänen aikaisemmistaan. Hän halusi lähteä sotaan Bysanttia vastaan eikä jäädä odottamaan heitä Yathribissa. Hän antoi yleisen käskyn käydä aseisiin määräten jopa vast'ikään valloitetun Mekan lähettämään joukkoja. Muhammad julisti, että Jumala oli määrännyt kaikki kynnelle kykenevät miehet taistelemaan Hänen asiansa puolesta tai heitä kohtaisi Jumalan tai hänen lähettiläänsä rangaistus. Hän sepitti uusia jihad-säkeitä antamaan pontta uhkauksilleen. Hän kutsui lähimmät miehensä paikalle ja vaati heiltä kaikilta osallistumista. Uthman toimitti useita satoja kuormakameleita, samoin tuhat kultakolikkoa. Abu Bakr antoi säkillisen hopearahoja; naiset lahjoittivat kultaisia ranne- ja nilkkarenkaitaan; toiset toivat kamelilasteittain viljaa ja taateleita. Pakollisesta "almujen antamisesta" oli tullut sotavero ja se perittiin kaikilta Muhammadin alistamilta heimoilta.
Huolimatta jumalallisen rangaistuksen uhasta Muhammad kohtasi vastustusta. Monet yathribilaiset eivät halunneet lähteä sotaan. Yksi heidän perusteluistaan oli keskikesän tukahduttava kuumuus, jossa Muhammad aikoi marssia kuusi ja puolisataa kilometriä Syyriaan polttavien hiekkakenttien yli. Muhammad julisti saarnastuolista, että nämä vastustelijat olivat "teeskentelijöitä" ja kirjoitti muutamia säkeitä näistä, jotka sanoivat olevansa uskovaisia, mutta jotka paljastivat itsensä kieltäytymällä tottelemasta.
Kerran hän meni sanallista pelottelua pidemmälle ottamalla käyttöön taktiikan, jota oli hiljattain käyttänyt saadakseen ihmiset osallistumaan aamun ja myöhäisillan rukoushetkiin: hän oli polttanut talot niiltä, jotka eivät olleet tulleet paikalle, asukkaiden ollessa vielä sisällä. Niinpä kun hän sai tietää, että joukko toisinajattelijoita oli kokoontunut juutalaisen käännynnäisen kotiin järjestelemään vastarintaa sotaretkeä vastaan, hän lähetti partion kiihkouskovaisia polttamaan talon. Kerrotaan, että vain juutalainen käännynnäinen kuoli palossa, mutta muilta katkesi luita heidän hypättyään katolta. Huolimatta näistä voimakeinoista väki tuli silti anomaan häneltä vapautusta palveluksesta esittäen syyksi sairauden, köyhyyden, perheongelmat ja monia muita syitä. Erikoisin tekosyy tuli eräältä mieheltä, joka sanoi, että bysanttilaiset naiset houkuttelisivat hänet tekemään syntiä, jos hän vain vilkaisisikin heitä, sillä bysantin naiset olivat kuuluisia Muhammadin Maria-vaimon tapaan vaaleasta kauneudestaan ja viettelevistä silmistään. Muhammad myönsi vapautuksen sitä pyytäneille, mutta laittoi heidän nimensä korvan taakse myöhempiä rangaistustoimia varten.
Ajoituksen ja Bysantin ilmeisen ylivoimaisuuden tähden tämä sotaretki "keltanahkoja" vastaan, jolla nimellä vaaleita bysanttilaisia kutsuttiin, on perusteltu vain Muhammadin epätoivoisena siirtona, sillä hän pelkäsi menettävänsä Yathribin kontrollin. Hänen hallintoonsa oltiin enenevässä määrin tyytymättömiä. Näin erityisesti monien Yathribin käännynäisten mielissä Mekan ja Hunain valloituksien jälkeen. He olivat hoitaneet taistelemisen, mutta Muhammad oli antanut Mekkalaisille parhaimmat osuudet sotasaaliista ja palauttanut Hawazineille suuren osan varmistaakseen heidän uskollisuutensa, jättäen Yathribin käännynnäisille vain tähteitä. Hän oli luvannut valloittaa Bahrainin heille ja antaa heille etuoikeuden ryöstelyyn, mutta kun he olivat palanneet Yathribiin, ei asiasta puhuttu enää mitään. Lisäksi Muhammadin menestys oli aiheuttanut köyhien käännynnäisten virtaamisen Yathribiin samaan aikaan, kun maatalouden tuotto väheni. Kuten aikaisemmin on todettu, hän oli karkoittanut tai surmannut laakson tuottavimmat asukkaat - juutalaiset - ja jakanut heidän peltonsa ja viljelyksensä mekkalaisille maanmiehilleen, miehille, joilla ei ollut aikaisempaa kokemusta maanviljelystä ja jotka tunsivat vastenmielisyyttä ruumillista työtä kohtaan. Seurauksena oli ruuan tuotannon väheneminen. Tämän lisäksi Muhammadilla oli vielä pitkäaikainen ongelma "teeskentelijöistä", jotka piileskelivät shahadan suojissa. Khazrajin päällikön Abdullah Ubayyn johdolla he saavuttivat vaikutusvaltaa ja olivat valmiita käyttämään kaikki virheet hyväkseen. Muhammad toivoi pystyvänsä suurella voitolla bysanttilaisista nostamaan moraalia, ja ryöstämään samalla riittävästi saalista pitääkseen väkensä tyytyväisenä.
Hänen pelkonsa Yathribin hallinnan menetyksestä kasvoi, kun armeija lähti kohti Syyriaa. Kokoontumisalueena toimi vuorisola vähän Yathribin pohjoispuolella, nimeltään Hyvästien sola. Abdullah Ubayy oli ollut leiriytyneenä siellä joukkoineen, mutta sinä päivänä, kun Muhammad lähti liikkeelle armeijansa edellä, Abdullah teki samoin kuin oli tehnyt Uhudissa: hän palasi Yathribiin ottaen uskollisimmat miehensä mukaansa. Muhammad oli jättänyt salamurhaaja Maslaman johtamaan Yathribia hänen poissa ollessaan, mutta nyt hän lähetti Alin pitämään silmällä asioita, hyvin luultavasti "varotoimena (Abdullah Ubayyn) kunnianhimoja vastaan ja kukistamaan mahdolliset kapinat", kuten sotahistorioitsija Richard Gabriel toteaa.
Kirjallisuus väittää, että sotaretkeen otti osaa kolmekymmentätuhatta miestä, ja että jälkijoukko kulki kaksi päivää etujoukon jäljessä. Myöhässä lähteneet ponnistelivat vieläkin jäljempänä. Kuumuuden vuoksi armeija marssi öisin ja suojautui auringolta päivisin. Syyria oli yli kuudensadan kilometrin päässä, mutta Muhammad ei päässyt sen pidemmälle kuin Tabukin pienelle keitaalle viisisataakolmekymmentä kilometriä Yathribista pohjoiseen. Kirjallisuudessa sanotaan, että Muhammad vietti keitaalla kymmenen päivää, hänen joukkonsa tekivät monia ryöstöretkiä, mutta sitten armeija palasi Yathribiin tapaamatta yhtäkään keltanahkaa; ainuttakaan dinaaria ei oltu saatu ryöstösaaliina; eikä yhtäkään naista saatu vangiksi. Mitään selitystä ei anneta sotaretken keskeytykseen, mutta monista Muhammadin tekemiksi väitetyistä veteen ja ruokaan liittyvistä ihmeistä voidaan päätellä, että armeijalla oli vaarallinen pula molemmista. Matkan jatkaminen Syyriaan olisi luultavasti aiheuttanut huomattavia miestappioita janon ja karkuruuden vuoksi. Muhammad on myös saattanut saada tiedustelutietoa, että Bysantin armeija ei ollutkaan Balqassa, kuten hän oli olettanut, mutta paljon kauempana pohjoisessa, eikä se ollut liikekannalla.
Tämä tapahtumien käänne sai Muhammadin näyttämään epäpätevältä, ja hän joutui kohtaamaan uuden ja mahdollisesti vaarallisemman vihollisen tyytymättömien miestensä joukossa. On epätodennäköistä, että edes kymmenen prosenttia miehistä uskoi hänen väitettään itsestään. Sen lisäksi, että heitä oli uhattu rangaistuksilla elleivät he osallistuisi sotaretkeen, useimpien pääasiallinen kannustin oli sotasaalis. Useimmat olivat käyttäneet omia rahojaan ja resurssejaan varustaakseen itsensä; he olivat kestäneet paahtavaa kuumuutta, matkan vaivoja sekä veden ja ruuan puutetta. Silti he eivät olleet kostuneet mitään, aivan samoin kuin he eivät olleet kostuneet mitään Mekasta, Hunainista tai Taifista. Jopa tosiuskovien usko joutui koetukselle. Muhammad yritti laannuttaa tyytymättömyyttä saarnoilla, joissa hänen Aabrahamin uskontonsa oli paras uskonto, hänen oma esimerkkinsä oli paras elämäntapa, Koraani oli paras kertomus Jumalasta ja jaloin kuolema oli kuolla Allahin asian puolesta.
Hänen maanläheisempiä toimiaan oli lähettää ryöstöpartioita ympäröiviin kaupunkeihin ja heimojen asuinalueille viestinään: alistukaa tai tuhoutukaa. Kristityille ja juutalaisille hän antoi vaihtoehdoiksi joko kääntyä islamiin tai maksaa alamaisveroa. Pakanoille tällaista mahdollisuutta ei annettu. Heidän oli joko luovuttava kuvainpalvonnastaan ja otettava Muhammadin uskonto tai heidät tapettaisiin.
Sotasaaliin haalimisen kannalta nämä retket epäonnistuivat. Kristityt, juutalaiset ja monijumalaiset antautuivat Muhammadin ylivoiman edessä. Suuret alueet Tabukista pohjoiseen sekä länteen Punaiselle merelle ja Aqaban lahdelle olivat kristittyjä. Sen sijaan, että olisivat ryhtyneet epätoivoiseen vastarintaan, kaupunkien piispat ja kuninkaat laittoivat matkaan lähettiläänsä neuvottelemaan Muhammadin kanssa alamaisveron maksamisesta siitä hyvästä, että heidät jätettäisiin rauhaan. Vero oli yksi kultaraha henkeä kohden vuodessa ja se maksettiin kuukalenterin mukaan vuoden ensimmäisenä kuukautena. Monet kaupungit joutuivat myös antamaan osuuden maataloustuotteista tai muista tuotetuista tavaroista kuten Jarba- ja Adru-heimojen kankaista ja hajusteista.
Vaikka nämä antautumiset edistivätkin Muhammadin tavoitetta, hänen miehensä olivat edelleen ilman palkkaa. Tyytymättömyyden on täytynyt olla suurta, sillä Muhammad joutui lopulta pelkäämään henkensä puolesta. Hänestä tuli vainoharhainen ja hän saattoi epäillä jopa lähimpien miestensä vehkeilevän häntä vastaan. Paluumatkalla tapahtui joko todellinen tai kuviteltu salamurhayritys, kun Muhammad laskeutui jyrkkää polkua, jonka toisella puolella oli syvä rotko. Hän oli antanut määräyksen, että ainoastaan kaksi hänen luotettavinta miestään sai laskeutua hänen kanssaan yhtä matkaa toisen taluttaessa kameliaan suitsista ja toisen tullessa jäljessä; muun armeijan tuli ottaa toinen reitti. Käskystä huolimatta kymmenkunta ratsastajaa ilmestyi polun yläpäähän. He olivat kietoneet turbaaniensa kankaan kasvojensa peitoksi niin, että vain silmät näkyivät. Muhammadista näytti siltä kuin he olisivat ottaneet linkoja esiin. Hän oli varma, että he aikoivat pillastuttaa lingoilla hänen kamelinsa niin, että se ryntäisi rotkoon vieden hänet mukanaan, tai sitten he tulisivat ja työntäisivät hänet kameleineen syvyyteen. Hän huusi heille kirouksia ja lähetti häntä saattavat kaksi luotettua miestä, aikaisia mekkalaisia käännynnäisiä, ratsastajien kimppuun, mutta nämä pakenivat ennen kuin miehet saavuttivat heidät. Muhammadilla oli epäilyksiä miesten henkilöllisyydestä ja mainitsi heidät Hudhaifalle, toiselle saattajistaan. Hudhaifa tarjoutui surmaamaan heidät, mutta Muhammad pudisti päätään. Hän ei halunnut tulla tunnetuksi profeettana, joka surmasi kumppaneitaan. Allah kyllä pitäisi heistä huolen ja lähettäisi heidän päälleen salamoita, jotta he saisivat esimakua siitä, mikä heitä odottaa ikuisessa tulessa. Koska ei ollut varma miesten henkilöydestä, hän vannotti Hudhaifaa pitämään asian salaisuutena, mutta piti samalla huolen siitä, että kaikki tiesivät Hudhaifan tietävän nimet, estääkseen uudet yritykset.
Tämä asia huipentui Muhammadin vainoharhaisuuteen niitä petollisia ihmisiä kohtaan, jotka piiloutuivat shahadan suojaan. Joidenkin, kuten Abdullah Ubayyn, henkilöllisyydestä hän oli varma, mutta muut pitäisi vielä paljastaa. Ennen kuin he saapuivat Yathribiin, hän päätti, että hiljattain Quban lähelle, ylängön lounaiskulmaan rakennettu moskeija oli väärän uskon ja salaliittolaisten pesä. Se oli saatu valmiiksi juuri ennen kuin armeija lähti bysanttilaisia vastaan, ja moskeijan rakentajat olivat pyytäneet häntä rukoilemaan moskeijassa ja antamaan sille siunauksensa. He sanoivat, ettei se ollut ainoastaan moskeija, vaan myös turvapaikka köyhille ja sairaille. Ennen saapumistaan Yathribiin Muhammad sai kuitenkin "ilmestyksen", jossa hänelle kerrottiin, että temppelin todellinen tarkoitus oli pahansuopa. Todisteet iskivät häneen kuin salama: ne kymmenkunta miestä, jotka olivat rakentaneet sen, olivat Aus-heimosta eikä kukaan heistä ollut lähtenyt armeijan mukaan. Se leimasi heidät automaattisesti teeskentelijöiksi. Lisäksi hän sai vielä tietää, että moskeija oli rakennettu Abu Amirin, kristityn käännynnäisen ja vannoutuneen Muhammadin vastustajan, kodin yhteyteen. Abu Amir oli kääntynyt kristinuskoon ennen kuin Muhammad oli saapunut Yathribiin ja omaksunut askeettisen elämäntyylin, josta hänelle oli annettu liikanimeksi "Munkki". Badrin taistelun jälkeen Munkki oli paennut joidenkin tukijoidensa kanssa Mekkaan, ja he taistelivat Uhudissa mekkalaisten rinnalla. Myöhemmin Abu Amir oli paennut Syyriaan, missä hänen sanottiin kehottaneen Herakleiosta käymään sotaan Muhammadia vastaan. Mikä muu tämä moskeija voisi olla kuin bysanttilaisten etuvartio Yathribissa, missä toisinajattelijat ja vallankumoukselliset kokoontuivat, kaikki katalia teeskentelijöitä. Muhammad nimesi sen "vastustuksen moskeijaksi". "Menkää tuohon moskeijaan, jonka ihmiset ovat pahoja, ja hävittäkää se ja polttakaa se!", hän komensi. Ainakin yksi mies paloi kuoliaaksi moskeijan sisällä. "Jopa hänen pallinsa olivat palaneet", eräs tuhopolttajista muisteli jälkeenpäin.
Jo päiviä ennen kuin Muhammad saapui Yathribiin, oli kaupunkia varoitettu, että hän oli raivoissaan. Edeltäpäin Yathribiin tulleet lähetit olivat levittäneet tietoa, että "teeskentelijät" olivat yrittäneet tappaa hänet, ja hän aikoi ottaa käsittelyyn valheelliset uskovaiset kunhan tulisi takaisin. Uutiset aiheuttivat paniikin. Jopa ennen kuin "vastustuksen moskeija" oli hävitetty, seitsemän miestä, jotka eivät olleet lähteneet armeijan mukaan, sitoivat itsensä pylväisiin Muhammadin moskeijan sisällä ja julistivat, että pysyisivät sidottuina kunnes Jumala ja hänen lähettiläänsä antaisivat heille anteeksi, että he olivat kieltäytyneet taistelemasta Allahin asian puolesta. He tunnustivat olleensa laiskoja. He olivat vitkastelijoita ja syntisiä, mutta heidän sydämensä olivat uskollisia ja vilpittömiä rakkaudessaan Jumalaa ja hänen lähettilästään kohtaan. Kun Muhammad, pölyn peitossa matkan jäljiltä, astui moskeijan sisäpihalle ja näki rivin sidottuja miehiä, hän sanoi: "Vannon Jumalan nimeen, etten vapauta heitä, enkä anna heille anteeksi ennen kuin Jumala, Kaikkivaltias ja Mahtava, vapauttaa heidät!" Hän antoi heidän kypsyä muutaman päivän ja sepitti sitten säkeen, jossa ylistettiin heitä heidän hyvästä teostaan, kun olivat tunnustaneet syntinsä. "On myös toisia, jotka tunnustavat syntinsä. He sekoittavat teon, joka on hyvä, toiseen, joka on paha. Jumala saattaa kääntää tämän heidän hyväkseen. Totisesti, Jumala on anteeksiantavainen, armollinen." Ja sitten hän päästi heidät menemään.
Vaatimus lähteä sotaretkelle "asian" puolesta oli Muhammadin versio lojaalisuustestistä. Taisteluun käyminen, tappaminen ja tapetuksi tuleminen, oli todiste uskollisuudesta; kieltäytyminen taistelemasta oli todistus petturuudesta. Useimmat Muhammadin seuraajista läpäisivät testin osallistumalla Tabukin sotaretkeen. Ne, jotka eivät olleet osallistuneet, joutuivat käymään läpi kovan uudelleenkoulutuksen, häpäisemisen ja ulkopuolelle sulkemisen, ennen kuin heidät hyväksyttiin katuvina ja päät alas painuneina takaisin riviin. Sillä aikaa kun nuo miehet olivat sidottuina moskeijassa, suuri joukko miehiä - yhteensä noin kahdeksankymmentä - tulivat Muhammadin eteen selittämään syynsä olla tottelematta hänen käskyään lähteä armeijan mukaan. Hän otti heidät vastaan yksitellen hymyillen vihaisesti ja antoi heidän istua edessään ja selittää poissaolonsa sotaretkeltä. "Mikä piteli sinua?" Muutamia lukuunottamatta kaikki antoivat yksityiskohtaiset perustelut. Muhammad lähetti heidät pois varoittaen, että Jumala kyllä tietäisi olivatko he puhuneet totta. Hän laittoi tiedustelijansa selvittämään heidän väitteidensä totuuden mukaisuuden, ja nämä raportoivat, että kolmekymmentäkuusi heistä oli valehdellut. Eräässä seurakunnan kokouksessa Muhammad sitten antoi tuomionsa. Hän julisti saarnastuolista: "Teidän joukossanne on teeskentelijöitä!" Hän nimesi kaikki kolmekymmentäkuusi miestä ja käski heidät seisomaan, jotta kaikki voisivat nähdä heidät. Kun nimet kuulutettiin, miehet nousivat vastentahtoisesti ylös, jotkut peittivät kasvonsa. Muhammad tuomitsi heidän tottelemattomuuden syntinsä väkijoukon edessä ja jyrisi, että miesten oli etsittävä Jumalan anteeksiantoa. Järkyttyneinä ytimiään myöten jouduttuaan julkisesti tuomituiksi teeskentelijöiksi he tunnustivat syntinsä; jotkut itkivät. Kädet ojennettuina Muhammadia kohti he anoivat anteeksiantoa.
Näiden kolmenkymmenenkuuden miehen häpäiseminen oli melko vähäinen rangaistus verrattuna niiden kolmen miehen rangaistukseen, jotka olivat olleet rehellisiä kertoessaan omat perustelunsa olla lähtemättä sotaan. Kun heidät kutsuttiin Muhammadin eteen, he tunnustivat, ettei heillä ollut mitään puolustusta. He olivat syyllisiä tottelemattomuuteen Jumalaa ja hänen lähettilästään kohtaan. Vaikka kaikki kolme olivat esimerkillisiä uskovaisia, jotka olivat ottaneet osaa aikaisemmille sotaretkille, Muhammad teki heistä varoittavan esimerkin. Hän julisti, että Jumala oli määrännyt heidät kartettaviksi, suljettaviksi yhteisön ulkopuolelle lähes kahdeksi kuukaudeksi. Kaksi miehistä sulkeutui koteihinsa ja he itkivät suurimman osan aikaa. Kolmas mies, uskollinen Yathribin käännynnäinen nimeltään Kab Malik kävi edelleen markkinapaikalla ja jopa moskeijassa rukoilemassa, mutta kaikki, jopa hänen sukulaisensa, kohtelivat häntä kylmäkiskoisesti. He kieltäytyivät puhumasta hänelle ja jopa katsomasta häneen. Kun hän puhui heille, he katsoivat toiseen suuntaan. Oli kuin häntä ei enää olisi olemassa. Hän oli kuin haamu, jota kukaan ei huomannut. Moskeijassa hän yritti saada Muhammadin huomion, mutta vaikka sattuikin katsomaan hänen suuntaansa, katsoi profeetta suoraan hänen lävitseen. Rangaistuksen kestettyä sietämättömät neljäkymmentä päivää, tuli viestintuoja kolkuttamaan hänen oveaan ja kertomaan vielä uudesta rangaistuksesta: Muhammad kielsi häneltä seksuaalisen kanssakäymisen vaimonsa kanssa. Heidät oli erotettava. Tätä jatkui aina viidenteenkymmenenteen päivään saakka, jolloin Kab kuuli etäisen äänen huutavan "Iloitse Kab!" Hän oli kotitalonsa katolla rukoilemassa, kun tämä tapahtui, eikä hän tiennyt miten siihen suhtautua. Ääni tuli Sal-vuoren, moskeijan lähellä olevan kukkulan, joka oli toiminut tähystyspaikkana vallihaudan taistelun aikana, huipulta. Pian hänen ovelleen tultiin ilmoittamaan iloiset uutiset: Kaikkivaltias Jumala oli ilmoittanut Muhammadille, että Kab ja kaksi muuta miestä olivat saaneet anteeksi. Kab kiiruhti moskeijaan, missä Muhammad istui rukouspaikalla jalat ristittynä uskollisimpien seuraajiensa ympäröimänä. Monet heistä nousivat jaloilleen puristaakseen Kabin kättä ja onnitellakseen häntä. Muhammad sanoi hänelle: "Iloitse, sillä tämä on paras päivä sen jälkeen, kun äitisi synnytti sinut!" Jumala oli antanut hänelle anteeksi! Kab oli niin ylitsevuotavan kiitollinen, että hän tarjoutui antamaan hyväntekeväisyyteen koko omaisuutensa, jossa oli mukana hänen osuutensa monien taisteluiden ja ryöstöretkien saaliista, mukaanlukien Khaibarin saalis. Muhammad ensin hylkäsi hänen tarjouksensa, mutta hyväksyi sitten osan. "Pidä jotain omaisuudestasi, se on sinulle parhaaksi." Kab vastasi: "Pidän vain osuuteni Khaibarin sotasaaliista."
Kuten tavallista, Muhammad jätti Abdullah Ubayyn rauhaan, vaikka tämä oli jäänyt pois sotaretkeltä päivänä, jolloin armeija lähti Yathribista. Hän luultavasti pelkäsi tämän piilevää vaikutusvaltaa. Ongelma ratkesi kuitenkin itsestään, kun Abdullah kuoli, näköjään luonnollisista syistä, noin kuukausi sen jälkeen, kun Muhammad palasi Tabukista. Hautajaisissa Muhammad lausui rukouksia hänen puolestaan, mutta katui myöhemmin, että oli tällä tavoin kunnioittanut tätä Yathribin arkkiteeskentelijää, miestä, joka oli selviytynyt käyttämällä taitavasti hyväkseen shahadan suojaa. Ehkäpä Muhammad oli salaisesti ihaillut Abdullahia tämän pelattua korttinsa niin taitavasti, mutta jotkut tosiuskovaiset kyseenalaistivat Muhammadin rukoukset poismenneen puolesta. Tästä syystä hän sepitti Koraaniin säkeen, jossa hän nuhtelee itseään ja kieltää vastaavat lipsahdukset. "Älä milloinkaan rukoile heikäläisen puolesta, joka kuolee, äläkä pysähdy hänen hautansa ääreen. Totisesti he eivät uskoneet Jumalaan eivätkä Hänen sanansaattajaansa, ja he kuolivat, koska he olivat tottelemattomia."
Vaikka hänen alkuperäinen tavoitteensa taistella bysanttilaisten kanssa epäonnistuikin, Tabukin sotaretki mahdollisti Muhammadille pohjoisen Arabian valloituksen loppuun saattamisen. Valloitus oli alkanut kolme vuotta aikaisemmin, kun hän lähetti Abdul Rahmanin kukistamaan kristityn karavaanikaupungin Duman. Se jatkui hyökkäyksillä Tamimiin ja Tayyisiin, jotka olivat tärkeitä heimoja Duman kaakkoispuolella, ja nämä päätyivät lopulta Muhammadin hallintaan. Viimeisimpien antautumisten jälkeen hän kontrolloi nyt valtavaa pohjoista aluetta Punaiselta mereltä Aqaban lahteen ja Tamimin ja Tayyin alueita keskisessä pohjois-Arabiassa. Hän lähetti alueille hallintovirkamiehiä, Koraanin opettajia ja veronkantajia.
Muhammadin sotilaallisen voiman osoitus Tabukissa nopeutti Arabian antautumista hänen valtaansa. Ennen kuin hän lähti marssille Yathribista kolmenkymmenentuhannen miehen kanssa, ainoastaan vähäinen määrä heimojen ja klaanien edustajia oli tullut Yathribiin vannomaan uskollisuuttaan ja joko liittymään hänen uskontoonsa tai maksamaan alamaisveroa. Nyt nämä "lähetystöt", kuten kirjallisuus heitä kutsuu, toivat mukanaan jatkuvana virtana miehiä, jotka eivät halunneet joutua seuraavaksi Muhammadin sotaretken uhreiksi. Kerrotaan kuinka miehet nousivat moskeijan sisäpihalla kameliensa selästä ja kiirehtivät tarttumaan Muhammadin käteen ja suutelemaan sitä. Vaikka hän piti enemmän arvokkuutensa säilyttävistä miehistä, ei Muhammad milloinkaan torjunut nöyristelevääkään käytöstä, ja harvoin lähetti yhtäkään pelokasta heimonsa edustajaa matkaan antamatta mukaan reilusti hopeaa, rahoina tai harkkoina.
Hän nautti imartelusta, ja jopa entiset viholliset tiesivät, että hänen suosioonsa voisi päästä ylistämällä häntä, kuten tiesi mekkalainen runoilija Kab Zuhair, joka oli sepittänyt herjaavia runoja profeetasta. Mekan valloituksen aikoihin Muhammad määräsi hänet surmattavaksi tavattaessa. Zuhair pakeni etelä-Arabiaan, mutta kun kävi selväksi, ettei Muhammadia voisi vältellä loputtomiin, hän tuli Yathribiin muiden vierailijoiden mukana pyytämään anteeksi aikaisempia vihollisuuksiaan. Moskeijan sisäpihalla hän julistautui uskovaiseksi väkijoukon edessä ja lausui ylitsevuotavan oodin, joka kuvaili Muhammadia "valon tuojaksi, Jumalan paljastetuksi miekaksi, parasta intialaista terästä." Vannomalla uskollisuutta Zuhair saavutti shahadan suojan. Imartelevalla runoudellaan hän sai paikan Muhammadin sydämestä.
Eteläinen osa Arabian niemimaata oli tähän asti pääosin säästynyt Muhammadin aggressiolta, mutta nyt siitä tuli laajentumisen kohde. Kuten aikaisemminkin, hän käytti yllätä-ja-peloita-taktiikkaa - "verenvuodatus maan päällä" - kuten hän sitä kutsui - tukahduttaakseen vastarinnan. Tämä vaihe alkoi jo kolme kuukautta ennen Tabukin sotaretkeä, kun hän lähetti joukon kiihkomielisiä uskovaisia tekemään yllätyshyökkäyksen vuoristoista heimoa vastaan, alueelle, joka nykyisin tunnetaan Saudi-Arabian Asirin maakuntana. He hyökkäsivät aamun koittaessa, tappaen niin monia kuin pystyivät, ja lähtivät saaliinaan sataviisikymmentä kamelia, kolmetuhatta vuohta, sekä joitakin naisia. Tätä seurasi Alin johtama retki lähelle Sanaa, Jemenin sydämeen. Hänen ratsuväkensä otti yhteen paikallisen heimon kanssa ja poistui voittajana surmattuaan kaksikymmentä heimolaista.
Muutamaa kuukautta myöhemmin Muhammad iski taas. Tällä kertaa Jurashiin, muinaiseen karavaanikaupunkiin ja Asirin alueen taloudelliseen keskukseen. Tämän ryöstöretken suoritti paikallinen heimopäällikkö Surad, joka oli käynyt Yathribissa vannomassa uskollisuutta Muhammadille. Hänet lähetettiin takaisin Jemeniin ohjeistuksella käydä sotaan monijumalaisia naapureitaan vastaan Muhammadin nimessä, mutta hänen oli käsketty ottaa sivuun viidennes sotasaaliista Muhammadille. Päästyään takaisin Jemeniin Surad kokosi armeijan ja piiritti Jurashia kokonaisen kuukauden. Koska ei kyennyt murtamaan muureja tai pakottamaan piiritettyjä antautumaan, hän vetäytyi suurieleisesti joukkojensa kanssa, mutta jäi odottamaan vuorille kunnes kaupungin asukkaat tulivat ulos, ja silloin hän hyökkäsi ja surmasi kaikki. Nyt oli käynyt niin, että Jurash oli myös lähettänyt lähetystön Muhammedin luo ennen kuin he tiesivät Muhammadin määränneen hyökkäyksen heitä vastaan. Lähetystön on täytynyt kulkea ristiin Suradin kanssa, joka oli matkalla kotiin tekemään sotavalmisteluita. Sillä aikaa kun Jurashin lähettiläät neuvottelivat Muhammadin kanssa, Surad surmasi heidän väkeään. Kun Muhammad kertoi heille tästä, he kiirehtivät kotiin vain huomatakseen, että monet heidän maanmiehistään ja naapureistaan olivat joutuneet surmatuiksi. He palasivat Yathribiin ja kääntyivät Muhammadin uskontoon.
Samoihin aikoihin Muhammad lähetti toisen Jemeniläisen käännynnäisen hävittämään samoin Jurashin alueella sijaitsevan Dhu Khalasan temppelin, jota kutsuttiin "etelän Kaabaksi". Dhu Khalasa oli miespuolinen vastine jumalatar al-Latille, ja pyhäkkö oli vuosittainen pyhiinvaelluskohde monille etelän arabeille. Jemeniläinen käännynnäinen oli huomattava sheikki Bajila-heimosta, joka ylläpiti pyhäkköä. Hän onnistui tuhoamaan temppelin, mutta joutui surmaamaan kolmesataa miestä, jotka kiirehtivät puolustamaan rakastettua pyhättöään.
Näillä toimillaan Muhammad kukisti kaikki Jemenin uskonnolliset ja taloudelliset keskukset, ja jäljelle jääneet jemeniläiset panivat sen merkille. Tämän jälkeen Alin tai Khalidin tarvitsi ainoastaan näyttäytyä ratsuväkensä edessä ja iskun kohteena oleva väestö antautui, kuten tapahtui, kun Khalid pysähtyi suurehkon kristityn kaupungin Najranin portilla ja julisti: "Oi ihmiset, kääntykää islamiin ja olette turvassa." Najran päätyi maksamaan alamaisveroa, jotta saattoi pysyä kristittynä, mutta sen oli kuitenkin otettava vastaan saarnamiehiä, tuomareita ja veronkantajia. Siitä lähtien Yathribissa vierailevat lähetystöt puhuivat selkeästi eteläisiä ja itäisiä murteita. Hallitsijat Himyarista, Hadramautista, Omanista ja Bahrainista tulivat kumartamaan Muhammadia. Niille, jotka kääntyivät hänen uskontoonsa, hän antoi tehtäväksi käydä sotaan monijumalaisia vastaan, ja milloin he niin tekivät, hän lähetti heille kirjeen ja onnitteli heitä vääräuskoisten surmaamisesta.
Sotasaalis oli ollut aikaisemmin Muhammadin kultin laajentumisen yllyke, mutta menestys aiheutti, että ryöstelyn mahdollisuudet supistuivat; valloitukset tekivät kuitenkin veroista tärkeän tulonlähteen. Kristityt ja juutalaiset, jotka kieltäytyivät kääntymästä, maksoivat henkiveroa kultana, hopeana, maataloustuotteina tai muina hyödykkeinä. Käännynnäiset maksoivat veroa, jota Muhammad kutsui hyväntekeväisyydeksi, vaikka todellisuudessa varat menivät yleiseen rahastoon ja suuri osa siitä päätyi sodankäynnin rahoittamiseen. Ajan myötä Muhammadin tulot alkoivat tulla veroista ryöstösaaliin sijasta.
Jemeniin lähetettiin vielä joitakin partioita, mutta ne olivat enemmänkin jäljellä olevien vastustajien pesäkkeiden siivousoperaatioita. Vuosi ennen kuolemaansa kesäkuussa 632 Muhammad oli koko Arabian niemimaan de facto hallitsija, ja hänen monoteismin lahkostaan oli tullut virallinen uskonto. Hänen yksinkertaisesta savitiilisestä moskeijastaan ja olkikattoisesta talostaan ja suuresta aidatusta sisäpihastaan tuli hänen valtakuntansa poliittinen ja hallinnollinen keskus.
Muhammad ylpeili usein menestyksellään, mikä on tallennettu moniin kirjoituksiin: "Pelko (jota kylvetään vihollisten sydämiin) on tehnyt minusta voittoisan, ja kun minä nukuin, maailman aarteiden avaimet tuotiin minulle ja pantiin minun käteeni."
Tultuaan alas majastaan Muhammad ei tuhlannut aikaa kootessaan armeijan, joka oli suurempi kuin mikään hänen aikaisemmistaan. Hän halusi lähteä sotaan Bysanttia vastaan eikä jäädä odottamaan heitä Yathribissa. Hän antoi yleisen käskyn käydä aseisiin määräten jopa vast'ikään valloitetun Mekan lähettämään joukkoja. Muhammad julisti, että Jumala oli määrännyt kaikki kynnelle kykenevät miehet taistelemaan Hänen asiansa puolesta tai heitä kohtaisi Jumalan tai hänen lähettiläänsä rangaistus. Hän sepitti uusia jihad-säkeitä antamaan pontta uhkauksilleen. Hän kutsui lähimmät miehensä paikalle ja vaati heiltä kaikilta osallistumista. Uthman toimitti useita satoja kuormakameleita, samoin tuhat kultakolikkoa. Abu Bakr antoi säkillisen hopearahoja; naiset lahjoittivat kultaisia ranne- ja nilkkarenkaitaan; toiset toivat kamelilasteittain viljaa ja taateleita. Pakollisesta "almujen antamisesta" oli tullut sotavero ja se perittiin kaikilta Muhammadin alistamilta heimoilta.
Huolimatta jumalallisen rangaistuksen uhasta Muhammad kohtasi vastustusta. Monet yathribilaiset eivät halunneet lähteä sotaan. Yksi heidän perusteluistaan oli keskikesän tukahduttava kuumuus, jossa Muhammad aikoi marssia kuusi ja puolisataa kilometriä Syyriaan polttavien hiekkakenttien yli. Muhammad julisti saarnastuolista, että nämä vastustelijat olivat "teeskentelijöitä" ja kirjoitti muutamia säkeitä näistä, jotka sanoivat olevansa uskovaisia, mutta jotka paljastivat itsensä kieltäytymällä tottelemasta.
Kerran hän meni sanallista pelottelua pidemmälle ottamalla käyttöön taktiikan, jota oli hiljattain käyttänyt saadakseen ihmiset osallistumaan aamun ja myöhäisillan rukoushetkiin: hän oli polttanut talot niiltä, jotka eivät olleet tulleet paikalle, asukkaiden ollessa vielä sisällä. Niinpä kun hän sai tietää, että joukko toisinajattelijoita oli kokoontunut juutalaisen käännynnäisen kotiin järjestelemään vastarintaa sotaretkeä vastaan, hän lähetti partion kiihkouskovaisia polttamaan talon. Kerrotaan, että vain juutalainen käännynnäinen kuoli palossa, mutta muilta katkesi luita heidän hypättyään katolta. Huolimatta näistä voimakeinoista väki tuli silti anomaan häneltä vapautusta palveluksesta esittäen syyksi sairauden, köyhyyden, perheongelmat ja monia muita syitä. Erikoisin tekosyy tuli eräältä mieheltä, joka sanoi, että bysanttilaiset naiset houkuttelisivat hänet tekemään syntiä, jos hän vain vilkaisisikin heitä, sillä bysantin naiset olivat kuuluisia Muhammadin Maria-vaimon tapaan vaaleasta kauneudestaan ja viettelevistä silmistään. Muhammad myönsi vapautuksen sitä pyytäneille, mutta laittoi heidän nimensä korvan taakse myöhempiä rangaistustoimia varten.
Ajoituksen ja Bysantin ilmeisen ylivoimaisuuden tähden tämä sotaretki "keltanahkoja" vastaan, jolla nimellä vaaleita bysanttilaisia kutsuttiin, on perusteltu vain Muhammadin epätoivoisena siirtona, sillä hän pelkäsi menettävänsä Yathribin kontrollin. Hänen hallintoonsa oltiin enenevässä määrin tyytymättömiä. Näin erityisesti monien Yathribin käännynäisten mielissä Mekan ja Hunain valloituksien jälkeen. He olivat hoitaneet taistelemisen, mutta Muhammad oli antanut Mekkalaisille parhaimmat osuudet sotasaaliista ja palauttanut Hawazineille suuren osan varmistaakseen heidän uskollisuutensa, jättäen Yathribin käännynnäisille vain tähteitä. Hän oli luvannut valloittaa Bahrainin heille ja antaa heille etuoikeuden ryöstelyyn, mutta kun he olivat palanneet Yathribiin, ei asiasta puhuttu enää mitään. Lisäksi Muhammadin menestys oli aiheuttanut köyhien käännynnäisten virtaamisen Yathribiin samaan aikaan, kun maatalouden tuotto väheni. Kuten aikaisemmin on todettu, hän oli karkoittanut tai surmannut laakson tuottavimmat asukkaat - juutalaiset - ja jakanut heidän peltonsa ja viljelyksensä mekkalaisille maanmiehilleen, miehille, joilla ei ollut aikaisempaa kokemusta maanviljelystä ja jotka tunsivat vastenmielisyyttä ruumillista työtä kohtaan. Seurauksena oli ruuan tuotannon väheneminen. Tämän lisäksi Muhammadilla oli vielä pitkäaikainen ongelma "teeskentelijöistä", jotka piileskelivät shahadan suojissa. Khazrajin päällikön Abdullah Ubayyn johdolla he saavuttivat vaikutusvaltaa ja olivat valmiita käyttämään kaikki virheet hyväkseen. Muhammad toivoi pystyvänsä suurella voitolla bysanttilaisista nostamaan moraalia, ja ryöstämään samalla riittävästi saalista pitääkseen väkensä tyytyväisenä.
Hänen pelkonsa Yathribin hallinnan menetyksestä kasvoi, kun armeija lähti kohti Syyriaa. Kokoontumisalueena toimi vuorisola vähän Yathribin pohjoispuolella, nimeltään Hyvästien sola. Abdullah Ubayy oli ollut leiriytyneenä siellä joukkoineen, mutta sinä päivänä, kun Muhammad lähti liikkeelle armeijansa edellä, Abdullah teki samoin kuin oli tehnyt Uhudissa: hän palasi Yathribiin ottaen uskollisimmat miehensä mukaansa. Muhammad oli jättänyt salamurhaaja Maslaman johtamaan Yathribia hänen poissa ollessaan, mutta nyt hän lähetti Alin pitämään silmällä asioita, hyvin luultavasti "varotoimena (Abdullah Ubayyn) kunnianhimoja vastaan ja kukistamaan mahdolliset kapinat", kuten sotahistorioitsija Richard Gabriel toteaa.
Kirjallisuus väittää, että sotaretkeen otti osaa kolmekymmentätuhatta miestä, ja että jälkijoukko kulki kaksi päivää etujoukon jäljessä. Myöhässä lähteneet ponnistelivat vieläkin jäljempänä. Kuumuuden vuoksi armeija marssi öisin ja suojautui auringolta päivisin. Syyria oli yli kuudensadan kilometrin päässä, mutta Muhammad ei päässyt sen pidemmälle kuin Tabukin pienelle keitaalle viisisataakolmekymmentä kilometriä Yathribista pohjoiseen. Kirjallisuudessa sanotaan, että Muhammad vietti keitaalla kymmenen päivää, hänen joukkonsa tekivät monia ryöstöretkiä, mutta sitten armeija palasi Yathribiin tapaamatta yhtäkään keltanahkaa; ainuttakaan dinaaria ei oltu saatu ryöstösaaliina; eikä yhtäkään naista saatu vangiksi. Mitään selitystä ei anneta sotaretken keskeytykseen, mutta monista Muhammadin tekemiksi väitetyistä veteen ja ruokaan liittyvistä ihmeistä voidaan päätellä, että armeijalla oli vaarallinen pula molemmista. Matkan jatkaminen Syyriaan olisi luultavasti aiheuttanut huomattavia miestappioita janon ja karkuruuden vuoksi. Muhammad on myös saattanut saada tiedustelutietoa, että Bysantin armeija ei ollutkaan Balqassa, kuten hän oli olettanut, mutta paljon kauempana pohjoisessa, eikä se ollut liikekannalla.
Tämä tapahtumien käänne sai Muhammadin näyttämään epäpätevältä, ja hän joutui kohtaamaan uuden ja mahdollisesti vaarallisemman vihollisen tyytymättömien miestensä joukossa. On epätodennäköistä, että edes kymmenen prosenttia miehistä uskoi hänen väitettään itsestään. Sen lisäksi, että heitä oli uhattu rangaistuksilla elleivät he osallistuisi sotaretkeen, useimpien pääasiallinen kannustin oli sotasaalis. Useimmat olivat käyttäneet omia rahojaan ja resurssejaan varustaakseen itsensä; he olivat kestäneet paahtavaa kuumuutta, matkan vaivoja sekä veden ja ruuan puutetta. Silti he eivät olleet kostuneet mitään, aivan samoin kuin he eivät olleet kostuneet mitään Mekasta, Hunainista tai Taifista. Jopa tosiuskovien usko joutui koetukselle. Muhammad yritti laannuttaa tyytymättömyyttä saarnoilla, joissa hänen Aabrahamin uskontonsa oli paras uskonto, hänen oma esimerkkinsä oli paras elämäntapa, Koraani oli paras kertomus Jumalasta ja jaloin kuolema oli kuolla Allahin asian puolesta.
Hänen maanläheisempiä toimiaan oli lähettää ryöstöpartioita ympäröiviin kaupunkeihin ja heimojen asuinalueille viestinään: alistukaa tai tuhoutukaa. Kristityille ja juutalaisille hän antoi vaihtoehdoiksi joko kääntyä islamiin tai maksaa alamaisveroa. Pakanoille tällaista mahdollisuutta ei annettu. Heidän oli joko luovuttava kuvainpalvonnastaan ja otettava Muhammadin uskonto tai heidät tapettaisiin.
Sotasaaliin haalimisen kannalta nämä retket epäonnistuivat. Kristityt, juutalaiset ja monijumalaiset antautuivat Muhammadin ylivoiman edessä. Suuret alueet Tabukista pohjoiseen sekä länteen Punaiselle merelle ja Aqaban lahdelle olivat kristittyjä. Sen sijaan, että olisivat ryhtyneet epätoivoiseen vastarintaan, kaupunkien piispat ja kuninkaat laittoivat matkaan lähettiläänsä neuvottelemaan Muhammadin kanssa alamaisveron maksamisesta siitä hyvästä, että heidät jätettäisiin rauhaan. Vero oli yksi kultaraha henkeä kohden vuodessa ja se maksettiin kuukalenterin mukaan vuoden ensimmäisenä kuukautena. Monet kaupungit joutuivat myös antamaan osuuden maataloustuotteista tai muista tuotetuista tavaroista kuten Jarba- ja Adru-heimojen kankaista ja hajusteista.
Vaikka nämä antautumiset edistivätkin Muhammadin tavoitetta, hänen miehensä olivat edelleen ilman palkkaa. Tyytymättömyyden on täytynyt olla suurta, sillä Muhammad joutui lopulta pelkäämään henkensä puolesta. Hänestä tuli vainoharhainen ja hän saattoi epäillä jopa lähimpien miestensä vehkeilevän häntä vastaan. Paluumatkalla tapahtui joko todellinen tai kuviteltu salamurhayritys, kun Muhammad laskeutui jyrkkää polkua, jonka toisella puolella oli syvä rotko. Hän oli antanut määräyksen, että ainoastaan kaksi hänen luotettavinta miestään sai laskeutua hänen kanssaan yhtä matkaa toisen taluttaessa kameliaan suitsista ja toisen tullessa jäljessä; muun armeijan tuli ottaa toinen reitti. Käskystä huolimatta kymmenkunta ratsastajaa ilmestyi polun yläpäähän. He olivat kietoneet turbaaniensa kankaan kasvojensa peitoksi niin, että vain silmät näkyivät. Muhammadista näytti siltä kuin he olisivat ottaneet linkoja esiin. Hän oli varma, että he aikoivat pillastuttaa lingoilla hänen kamelinsa niin, että se ryntäisi rotkoon vieden hänet mukanaan, tai sitten he tulisivat ja työntäisivät hänet kameleineen syvyyteen. Hän huusi heille kirouksia ja lähetti häntä saattavat kaksi luotettua miestä, aikaisia mekkalaisia käännynnäisiä, ratsastajien kimppuun, mutta nämä pakenivat ennen kuin miehet saavuttivat heidät. Muhammadilla oli epäilyksiä miesten henkilöllisyydestä ja mainitsi heidät Hudhaifalle, toiselle saattajistaan. Hudhaifa tarjoutui surmaamaan heidät, mutta Muhammad pudisti päätään. Hän ei halunnut tulla tunnetuksi profeettana, joka surmasi kumppaneitaan. Allah kyllä pitäisi heistä huolen ja lähettäisi heidän päälleen salamoita, jotta he saisivat esimakua siitä, mikä heitä odottaa ikuisessa tulessa. Koska ei ollut varma miesten henkilöydestä, hän vannotti Hudhaifaa pitämään asian salaisuutena, mutta piti samalla huolen siitä, että kaikki tiesivät Hudhaifan tietävän nimet, estääkseen uudet yritykset.
Tämä asia huipentui Muhammadin vainoharhaisuuteen niitä petollisia ihmisiä kohtaan, jotka piiloutuivat shahadan suojaan. Joidenkin, kuten Abdullah Ubayyn, henkilöllisyydestä hän oli varma, mutta muut pitäisi vielä paljastaa. Ennen kuin he saapuivat Yathribiin, hän päätti, että hiljattain Quban lähelle, ylängön lounaiskulmaan rakennettu moskeija oli väärän uskon ja salaliittolaisten pesä. Se oli saatu valmiiksi juuri ennen kuin armeija lähti bysanttilaisia vastaan, ja moskeijan rakentajat olivat pyytäneet häntä rukoilemaan moskeijassa ja antamaan sille siunauksensa. He sanoivat, ettei se ollut ainoastaan moskeija, vaan myös turvapaikka köyhille ja sairaille. Ennen saapumistaan Yathribiin Muhammad sai kuitenkin "ilmestyksen", jossa hänelle kerrottiin, että temppelin todellinen tarkoitus oli pahansuopa. Todisteet iskivät häneen kuin salama: ne kymmenkunta miestä, jotka olivat rakentaneet sen, olivat Aus-heimosta eikä kukaan heistä ollut lähtenyt armeijan mukaan. Se leimasi heidät automaattisesti teeskentelijöiksi. Lisäksi hän sai vielä tietää, että moskeija oli rakennettu Abu Amirin, kristityn käännynnäisen ja vannoutuneen Muhammadin vastustajan, kodin yhteyteen. Abu Amir oli kääntynyt kristinuskoon ennen kuin Muhammad oli saapunut Yathribiin ja omaksunut askeettisen elämäntyylin, josta hänelle oli annettu liikanimeksi "Munkki". Badrin taistelun jälkeen Munkki oli paennut joidenkin tukijoidensa kanssa Mekkaan, ja he taistelivat Uhudissa mekkalaisten rinnalla. Myöhemmin Abu Amir oli paennut Syyriaan, missä hänen sanottiin kehottaneen Herakleiosta käymään sotaan Muhammadia vastaan. Mikä muu tämä moskeija voisi olla kuin bysanttilaisten etuvartio Yathribissa, missä toisinajattelijat ja vallankumoukselliset kokoontuivat, kaikki katalia teeskentelijöitä. Muhammad nimesi sen "vastustuksen moskeijaksi". "Menkää tuohon moskeijaan, jonka ihmiset ovat pahoja, ja hävittäkää se ja polttakaa se!", hän komensi. Ainakin yksi mies paloi kuoliaaksi moskeijan sisällä. "Jopa hänen pallinsa olivat palaneet", eräs tuhopolttajista muisteli jälkeenpäin.
Vaatimus lähteä sotaretkelle "asian" puolesta oli Muhammadin versio lojaalisuustestistä. Taisteluun käyminen, tappaminen ja tapetuksi tuleminen, oli todiste uskollisuudesta; kieltäytyminen taistelemasta oli todistus petturuudesta. Useimmat Muhammadin seuraajista läpäisivät testin osallistumalla Tabukin sotaretkeen. Ne, jotka eivät olleet osallistuneet, joutuivat käymään läpi kovan uudelleenkoulutuksen, häpäisemisen ja ulkopuolelle sulkemisen, ennen kuin heidät hyväksyttiin katuvina ja päät alas painuneina takaisin riviin. Sillä aikaa kun nuo miehet olivat sidottuina moskeijassa, suuri joukko miehiä - yhteensä noin kahdeksankymmentä - tulivat Muhammadin eteen selittämään syynsä olla tottelematta hänen käskyään lähteä armeijan mukaan. Hän otti heidät vastaan yksitellen hymyillen vihaisesti ja antoi heidän istua edessään ja selittää poissaolonsa sotaretkeltä. "Mikä piteli sinua?" Muutamia lukuunottamatta kaikki antoivat yksityiskohtaiset perustelut. Muhammad lähetti heidät pois varoittaen, että Jumala kyllä tietäisi olivatko he puhuneet totta. Hän laittoi tiedustelijansa selvittämään heidän väitteidensä totuuden mukaisuuden, ja nämä raportoivat, että kolmekymmentäkuusi heistä oli valehdellut. Eräässä seurakunnan kokouksessa Muhammad sitten antoi tuomionsa. Hän julisti saarnastuolista: "Teidän joukossanne on teeskentelijöitä!" Hän nimesi kaikki kolmekymmentäkuusi miestä ja käski heidät seisomaan, jotta kaikki voisivat nähdä heidät. Kun nimet kuulutettiin, miehet nousivat vastentahtoisesti ylös, jotkut peittivät kasvonsa. Muhammad tuomitsi heidän tottelemattomuuden syntinsä väkijoukon edessä ja jyrisi, että miesten oli etsittävä Jumalan anteeksiantoa. Järkyttyneinä ytimiään myöten jouduttuaan julkisesti tuomituiksi teeskentelijöiksi he tunnustivat syntinsä; jotkut itkivät. Kädet ojennettuina Muhammadia kohti he anoivat anteeksiantoa.
Näiden kolmenkymmenenkuuden miehen häpäiseminen oli melko vähäinen rangaistus verrattuna niiden kolmen miehen rangaistukseen, jotka olivat olleet rehellisiä kertoessaan omat perustelunsa olla lähtemättä sotaan. Kun heidät kutsuttiin Muhammadin eteen, he tunnustivat, ettei heillä ollut mitään puolustusta. He olivat syyllisiä tottelemattomuuteen Jumalaa ja hänen lähettilästään kohtaan. Vaikka kaikki kolme olivat esimerkillisiä uskovaisia, jotka olivat ottaneet osaa aikaisemmille sotaretkille, Muhammad teki heistä varoittavan esimerkin. Hän julisti, että Jumala oli määrännyt heidät kartettaviksi, suljettaviksi yhteisön ulkopuolelle lähes kahdeksi kuukaudeksi. Kaksi miehistä sulkeutui koteihinsa ja he itkivät suurimman osan aikaa. Kolmas mies, uskollinen Yathribin käännynnäinen nimeltään Kab Malik kävi edelleen markkinapaikalla ja jopa moskeijassa rukoilemassa, mutta kaikki, jopa hänen sukulaisensa, kohtelivat häntä kylmäkiskoisesti. He kieltäytyivät puhumasta hänelle ja jopa katsomasta häneen. Kun hän puhui heille, he katsoivat toiseen suuntaan. Oli kuin häntä ei enää olisi olemassa. Hän oli kuin haamu, jota kukaan ei huomannut. Moskeijassa hän yritti saada Muhammadin huomion, mutta vaikka sattuikin katsomaan hänen suuntaansa, katsoi profeetta suoraan hänen lävitseen. Rangaistuksen kestettyä sietämättömät neljäkymmentä päivää, tuli viestintuoja kolkuttamaan hänen oveaan ja kertomaan vielä uudesta rangaistuksesta: Muhammad kielsi häneltä seksuaalisen kanssakäymisen vaimonsa kanssa. Heidät oli erotettava. Tätä jatkui aina viidenteenkymmenenteen päivään saakka, jolloin Kab kuuli etäisen äänen huutavan "Iloitse Kab!" Hän oli kotitalonsa katolla rukoilemassa, kun tämä tapahtui, eikä hän tiennyt miten siihen suhtautua. Ääni tuli Sal-vuoren, moskeijan lähellä olevan kukkulan, joka oli toiminut tähystyspaikkana vallihaudan taistelun aikana, huipulta. Pian hänen ovelleen tultiin ilmoittamaan iloiset uutiset: Kaikkivaltias Jumala oli ilmoittanut Muhammadille, että Kab ja kaksi muuta miestä olivat saaneet anteeksi. Kab kiiruhti moskeijaan, missä Muhammad istui rukouspaikalla jalat ristittynä uskollisimpien seuraajiensa ympäröimänä. Monet heistä nousivat jaloilleen puristaakseen Kabin kättä ja onnitellakseen häntä. Muhammad sanoi hänelle: "Iloitse, sillä tämä on paras päivä sen jälkeen, kun äitisi synnytti sinut!" Jumala oli antanut hänelle anteeksi! Kab oli niin ylitsevuotavan kiitollinen, että hän tarjoutui antamaan hyväntekeväisyyteen koko omaisuutensa, jossa oli mukana hänen osuutensa monien taisteluiden ja ryöstöretkien saaliista, mukaanlukien Khaibarin saalis. Muhammad ensin hylkäsi hänen tarjouksensa, mutta hyväksyi sitten osan. "Pidä jotain omaisuudestasi, se on sinulle parhaaksi." Kab vastasi: "Pidän vain osuuteni Khaibarin sotasaaliista."
Kuten tavallista, Muhammad jätti Abdullah Ubayyn rauhaan, vaikka tämä oli jäänyt pois sotaretkeltä päivänä, jolloin armeija lähti Yathribista. Hän luultavasti pelkäsi tämän piilevää vaikutusvaltaa. Ongelma ratkesi kuitenkin itsestään, kun Abdullah kuoli, näköjään luonnollisista syistä, noin kuukausi sen jälkeen, kun Muhammad palasi Tabukista. Hautajaisissa Muhammad lausui rukouksia hänen puolestaan, mutta katui myöhemmin, että oli tällä tavoin kunnioittanut tätä Yathribin arkkiteeskentelijää, miestä, joka oli selviytynyt käyttämällä taitavasti hyväkseen shahadan suojaa. Ehkäpä Muhammad oli salaisesti ihaillut Abdullahia tämän pelattua korttinsa niin taitavasti, mutta jotkut tosiuskovaiset kyseenalaistivat Muhammadin rukoukset poismenneen puolesta. Tästä syystä hän sepitti Koraaniin säkeen, jossa hän nuhtelee itseään ja kieltää vastaavat lipsahdukset. "Älä milloinkaan rukoile heikäläisen puolesta, joka kuolee, äläkä pysähdy hänen hautansa ääreen. Totisesti he eivät uskoneet Jumalaan eivätkä Hänen sanansaattajaansa, ja he kuolivat, koska he olivat tottelemattomia."
Vaikka hänen alkuperäinen tavoitteensa taistella bysanttilaisten kanssa epäonnistuikin, Tabukin sotaretki mahdollisti Muhammadille pohjoisen Arabian valloituksen loppuun saattamisen. Valloitus oli alkanut kolme vuotta aikaisemmin, kun hän lähetti Abdul Rahmanin kukistamaan kristityn karavaanikaupungin Duman. Se jatkui hyökkäyksillä Tamimiin ja Tayyisiin, jotka olivat tärkeitä heimoja Duman kaakkoispuolella, ja nämä päätyivät lopulta Muhammadin hallintaan. Viimeisimpien antautumisten jälkeen hän kontrolloi nyt valtavaa pohjoista aluetta Punaiselta mereltä Aqaban lahteen ja Tamimin ja Tayyin alueita keskisessä pohjois-Arabiassa. Hän lähetti alueille hallintovirkamiehiä, Koraanin opettajia ja veronkantajia.
Muhammadin sotilaallisen voiman osoitus Tabukissa nopeutti Arabian antautumista hänen valtaansa. Ennen kuin hän lähti marssille Yathribista kolmenkymmenentuhannen miehen kanssa, ainoastaan vähäinen määrä heimojen ja klaanien edustajia oli tullut Yathribiin vannomaan uskollisuuttaan ja joko liittymään hänen uskontoonsa tai maksamaan alamaisveroa. Nyt nämä "lähetystöt", kuten kirjallisuus heitä kutsuu, toivat mukanaan jatkuvana virtana miehiä, jotka eivät halunneet joutua seuraavaksi Muhammadin sotaretken uhreiksi. Kerrotaan kuinka miehet nousivat moskeijan sisäpihalla kameliensa selästä ja kiirehtivät tarttumaan Muhammadin käteen ja suutelemaan sitä. Vaikka hän piti enemmän arvokkuutensa säilyttävistä miehistä, ei Muhammad milloinkaan torjunut nöyristelevääkään käytöstä, ja harvoin lähetti yhtäkään pelokasta heimonsa edustajaa matkaan antamatta mukaan reilusti hopeaa, rahoina tai harkkoina.
Hän nautti imartelusta, ja jopa entiset viholliset tiesivät, että hänen suosioonsa voisi päästä ylistämällä häntä, kuten tiesi mekkalainen runoilija Kab Zuhair, joka oli sepittänyt herjaavia runoja profeetasta. Mekan valloituksen aikoihin Muhammad määräsi hänet surmattavaksi tavattaessa. Zuhair pakeni etelä-Arabiaan, mutta kun kävi selväksi, ettei Muhammadia voisi vältellä loputtomiin, hän tuli Yathribiin muiden vierailijoiden mukana pyytämään anteeksi aikaisempia vihollisuuksiaan. Moskeijan sisäpihalla hän julistautui uskovaiseksi väkijoukon edessä ja lausui ylitsevuotavan oodin, joka kuvaili Muhammadia "valon tuojaksi, Jumalan paljastetuksi miekaksi, parasta intialaista terästä." Vannomalla uskollisuutta Zuhair saavutti shahadan suojan. Imartelevalla runoudellaan hän sai paikan Muhammadin sydämestä.
Eteläinen osa Arabian niemimaata oli tähän asti pääosin säästynyt Muhammadin aggressiolta, mutta nyt siitä tuli laajentumisen kohde. Kuten aikaisemminkin, hän käytti yllätä-ja-peloita-taktiikkaa - "verenvuodatus maan päällä" - kuten hän sitä kutsui - tukahduttaakseen vastarinnan. Tämä vaihe alkoi jo kolme kuukautta ennen Tabukin sotaretkeä, kun hän lähetti joukon kiihkomielisiä uskovaisia tekemään yllätyshyökkäyksen vuoristoista heimoa vastaan, alueelle, joka nykyisin tunnetaan Saudi-Arabian Asirin maakuntana. He hyökkäsivät aamun koittaessa, tappaen niin monia kuin pystyivät, ja lähtivät saaliinaan sataviisikymmentä kamelia, kolmetuhatta vuohta, sekä joitakin naisia. Tätä seurasi Alin johtama retki lähelle Sanaa, Jemenin sydämeen. Hänen ratsuväkensä otti yhteen paikallisen heimon kanssa ja poistui voittajana surmattuaan kaksikymmentä heimolaista.
Muutamaa kuukautta myöhemmin Muhammad iski taas. Tällä kertaa Jurashiin, muinaiseen karavaanikaupunkiin ja Asirin alueen taloudelliseen keskukseen. Tämän ryöstöretken suoritti paikallinen heimopäällikkö Surad, joka oli käynyt Yathribissa vannomassa uskollisuutta Muhammadille. Hänet lähetettiin takaisin Jemeniin ohjeistuksella käydä sotaan monijumalaisia naapureitaan vastaan Muhammadin nimessä, mutta hänen oli käsketty ottaa sivuun viidennes sotasaaliista Muhammadille. Päästyään takaisin Jemeniin Surad kokosi armeijan ja piiritti Jurashia kokonaisen kuukauden. Koska ei kyennyt murtamaan muureja tai pakottamaan piiritettyjä antautumaan, hän vetäytyi suurieleisesti joukkojensa kanssa, mutta jäi odottamaan vuorille kunnes kaupungin asukkaat tulivat ulos, ja silloin hän hyökkäsi ja surmasi kaikki. Nyt oli käynyt niin, että Jurash oli myös lähettänyt lähetystön Muhammedin luo ennen kuin he tiesivät Muhammadin määränneen hyökkäyksen heitä vastaan. Lähetystön on täytynyt kulkea ristiin Suradin kanssa, joka oli matkalla kotiin tekemään sotavalmisteluita. Sillä aikaa kun Jurashin lähettiläät neuvottelivat Muhammadin kanssa, Surad surmasi heidän väkeään. Kun Muhammad kertoi heille tästä, he kiirehtivät kotiin vain huomatakseen, että monet heidän maanmiehistään ja naapureistaan olivat joutuneet surmatuiksi. He palasivat Yathribiin ja kääntyivät Muhammadin uskontoon.
Samoihin aikoihin Muhammad lähetti toisen Jemeniläisen käännynnäisen hävittämään samoin Jurashin alueella sijaitsevan Dhu Khalasan temppelin, jota kutsuttiin "etelän Kaabaksi". Dhu Khalasa oli miespuolinen vastine jumalatar al-Latille, ja pyhäkkö oli vuosittainen pyhiinvaelluskohde monille etelän arabeille. Jemeniläinen käännynnäinen oli huomattava sheikki Bajila-heimosta, joka ylläpiti pyhäkköä. Hän onnistui tuhoamaan temppelin, mutta joutui surmaamaan kolmesataa miestä, jotka kiirehtivät puolustamaan rakastettua pyhättöään.
Näillä toimillaan Muhammad kukisti kaikki Jemenin uskonnolliset ja taloudelliset keskukset, ja jäljelle jääneet jemeniläiset panivat sen merkille. Tämän jälkeen Alin tai Khalidin tarvitsi ainoastaan näyttäytyä ratsuväkensä edessä ja iskun kohteena oleva väestö antautui, kuten tapahtui, kun Khalid pysähtyi suurehkon kristityn kaupungin Najranin portilla ja julisti: "Oi ihmiset, kääntykää islamiin ja olette turvassa." Najran päätyi maksamaan alamaisveroa, jotta saattoi pysyä kristittynä, mutta sen oli kuitenkin otettava vastaan saarnamiehiä, tuomareita ja veronkantajia. Siitä lähtien Yathribissa vierailevat lähetystöt puhuivat selkeästi eteläisiä ja itäisiä murteita. Hallitsijat Himyarista, Hadramautista, Omanista ja Bahrainista tulivat kumartamaan Muhammadia. Niille, jotka kääntyivät hänen uskontoonsa, hän antoi tehtäväksi käydä sotaan monijumalaisia vastaan, ja milloin he niin tekivät, hän lähetti heille kirjeen ja onnitteli heitä vääräuskoisten surmaamisesta.
Sotasaalis oli ollut aikaisemmin Muhammadin kultin laajentumisen yllyke, mutta menestys aiheutti, että ryöstelyn mahdollisuudet supistuivat; valloitukset tekivät kuitenkin veroista tärkeän tulonlähteen. Kristityt ja juutalaiset, jotka kieltäytyivät kääntymästä, maksoivat henkiveroa kultana, hopeana, maataloustuotteina tai muina hyödykkeinä. Käännynnäiset maksoivat veroa, jota Muhammad kutsui hyväntekeväisyydeksi, vaikka todellisuudessa varat menivät yleiseen rahastoon ja suuri osa siitä päätyi sodankäynnin rahoittamiseen. Ajan myötä Muhammadin tulot alkoivat tulla veroista ryöstösaaliin sijasta.
Jemeniin lähetettiin vielä joitakin partioita, mutta ne olivat enemmänkin jäljellä olevien vastustajien pesäkkeiden siivousoperaatioita. Vuosi ennen kuolemaansa kesäkuussa 632 Muhammad oli koko Arabian niemimaan de facto hallitsija, ja hänen monoteismin lahkostaan oli tullut virallinen uskonto. Hänen yksinkertaisesta savitiilisestä moskeijastaan ja olkikattoisesta talostaan ja suuresta aidatusta sisäpihastaan tuli hänen valtakuntansa poliittinen ja hallinnollinen keskus.
Muhammad ylpeili usein menestyksellään, mikä on tallennettu moniin kirjoituksiin: "Pelko (jota kylvetään vihollisten sydämiin) on tehnyt minusta voittoisan, ja kun minä nukuin, maailman aarteiden avaimet tuotiin minulle ja pantiin minun käteeni."