Qureishilaiset olivat epäonnistuneet pyrkimyksissään tuhota islam. Muslimen luku kasvoi päivä päivältä ja heidän adrin aikainen 300 miehen armeijansa oli Uhudin taisteluun tultaessa kasvanut 700:ään; Vallihaudan taisteluun osallistui jo 3.000 muslimisoturia. Paastokuukauden, Ramadanin jälkeen Profeetta (SAWS) näki unen, joka viittasi siihen, että muslimien tulisi lähteä pyhiinvaellukselle Mekkaan. 1.400 muslimia valmistautui tekemään pienemmän pyhiinvaelluksen, umran. He pukeutuivat valkoisiin ja kulkivat ilman aseita osoittaakseen mekkalaisille tulleensa pyhiinvaellukselle, eivät sotimaan. Kun qureishilaiset kuulivat Profeetan (SAWS) olevan matkalla, he lähettivät Khalid ibn al-Walidin johtaman joukko-osaston estämään muslimien pääsyn kaupunkiin. Välttääkseen yhteenoton tämän pienehkön armeijan kanssa. Profeetta (SAWS) käänsi reitin kulkemaan vaikeakulkuisen vuoriston yli. Kun he vihdoin pääsivät helpompikulkuiselle alueelle hän sanoi väelleen: "Sanokaa, me pyydämme Allahin anteeksiantoa ja käännymme katuen Hänen puoleensa." Mekan eteläpuolella olevassa Hudaybiyassa Profeetan kameli polvistui ja kieltäytyi jatkamasta matkaansa. Muslimit arvelivat sen olevan joko jääräpäinen tai sitten matkasta uupunut. Profeetta (SAWS) oikaisi heidän ajatuksensa sanoen: "Sama voima, joka esti elefanttia menemästä Mekkaan, estää nyt meitä siitä!" Sitten antoi käskyn leiriytyä, joka pantiin toimeen, vaikka kaikki toivoivatkin voivansa seuraavana päivänä jatkaa matkaansa pyhään Ka’baan. Leiriytyessään muslimit harmikseen huomasivat vesilähteitten olevan lähes tyhjillään. Tämän kuultuaan Profeetta (SAWS) käski Najiah - nimistä miestä ottamaan vesiastian, jonka vedellä tämä oli puhdistautunut, ja kaatamaan sen sisältämän veden koloon, jossa oli vähänkin lähdevettä jäljellä. Seosta tuli hämmentää nuolella. Najiah teki työtä käskettyä. Tuskin hän oli edes alkanut sekoittaa, kun vettä alkoi suihkuta niin ettei sen alta tahtonut ehtiä pois. Viestinviejiä lähetettiin kertomaan qureishilaisille, että muslimit olivat tulleet pelkästään pyhiinvaellukselle, palvellakseen Allahia Pyhässä Ka'bassa. Tässä tarkoituksessa he tahtoivat vain päästä rauhassa kaupunkiin. Qureishilaiset eivät piitanneet vähääkään viesteistä. Lopulta Profeetan vävy, Uthman bin Affan, viisas ja arvostettu mies, valittiin sanansaattajaksi. Muslimit istuivat odottelemaan minkälaisen vastauksen kera tämä palaisi. Kun hänen paluunsa kuitenkin viipymistään viipyi, alkoivat muslimit käydä levottomiksi. Epäilys,että hänet olisi surmattu pääsi vallalle. Profeetan (SAWS) valtasi ilmestyksen saamiseen rinnastettava olotila. Hän keräsi musliminsa akaasiapuun alle, ja kehoitti näitä vannomaan uskollisuudenvalan. Sen he auliisti tekivätkin. Tämä Koraanissakin mainittu liitto, tunnettiin myöhemmin Radwan'in (tarkoittaa Paratiisia) sopimuksena. Jonkin ajan kulutta Uthman bin Affan kuitenkin palasi ja muslimit saattoivat huokaista helpotuksesta. Muutamat mekkalaissotilaat yrittivät hyökätä muslimien kimppuun. Heidät saatiin kuitenkin verekseltään kiinni ja tuotiin Profeetan (SAWS) eteen. Tämä antoi heille anteeksi, heidän luvattuaan lopettaa hyökkäilynsä muslimeita vastaan. Pian tämän jälkeen tulivat qureishilaisten viralliset edustajat paikalle. Välittömästi aloitettiin neuvottelut kiistan rauhanomaisesta ratkaisusta. Mekkalaiset lähettivät edustajakseen Suhayl ibn 'Amr nimisen miehen. Kun Profeetta (SAWS) pyysi 'Alia alkamaan tekstin sanoin Allahin, Armeliaan Armahtajan nimeen, Suhayl esitti vastalauseensa:" Kirjoita vain 'bismik Allahumma' (Sinun nimessäsi.Oi Allah). Minä en tunne Häntä nimillä Ar-raHman (Armelias) ar-raHiim (Armahtaja)." Profeetta (SAWS) myöntyi tähän, ja jatkoi saneluaan: "Tämä sopimus on laadittu Muhammedin, Allahin Lähettilään ja Suhayl bin 'Amrin toimesta." "Seis!" huudahti Suhayl, "En usko sinun olevan Rasulallah'in (Allahin Lähettilään); kuvitteletko, että voisin taistella sinua vastaan jos uskoisin niin?" Profeetta (SAWS) suostui tyynesti siihen, että hänestä käytettäisiin vain nimitystä Muhammed, Abd Allahin poika. Muslimit tuohtuivat tästä ja 'Umar tivasi: "Etkö siis olekaan Allahin Lähettiläs, ja emmekö me olekaan muslimeita? Kuinka me, jotka olemme oikeassa, saatamme myöntyä sellaiseen sopimukseen väärässä olevien kanssa? Ihmiset tulevat nauramaan uskonnollomme!" Profeetta (SAWS) kuitenkin tajusi mikä olisi parasta, ja niin Hudaybiyan sopimus allekirjoitettiin. Siinä kummatkin osapuolet sopivat lopettavansa vihollisuudet kymmeneksi vuodeksi. Sovittiin myös, että muslimit palaavat välittömästi Medinaan, mutta seuraavana vuonna heillä oli oikeus tulla kolmipäiväiselle pyhiinvaellukselle. Lisäksi sovittiin, että sellaiset muslimit, jotka olivat valmiit luopumaan islamista, voisivat palata Mekkaan. Mekkalaisilla puolestaan oli oikeus ryhtyä muslimeiksi ja siirtyä Medinaan, edellyttäen, että heidän suojelijansa tai holhoojansa siihen suostuvat. Muslimit suostuivat palauttamaan Mekkaan kaikki, joilla ei ollut suojelijoittensa tai holhoojiensa suostumusta olla Medinassa. Suhaylin oma poika oli tullut isänsä mukana leiriin liittyäkseen Profeetan (SAWS) seurueeseen. Allekirjoitetun sopimuksen nojalla hänen oli kuitenkin pakko palata Mekkaan. Hän itki päätöstä katkerasti. Profeetta (SAWS) lohdutti häntä: "Kuuelhan Abu Jandal, ole kärsivällisellä mielellä ja hillitse itsesi. Allah on suova helpotuksen ja näyttävä tien ulos, niin sinulle kuin kohtalotovereillesikin." Muslimien enemmistölle oli sopimusehtojen nieleminen katkera pala. Heidän mielestään sopimusta ei olisi tullut hyväksyä. He eivät kyenneet tajuamaan, että tehty sopimus oli itseasiassa suuri voitto Profeetalle (SAWS), jonka Allah sittemmin vahvisti ilmoituksessaan. Sopimuksella varmistettiin se, että muslimit voisivat seuraavana vuonna mennä kaikessa rauhassa Mekkaan. Ajan mittaan se merkitsi myös sitä, että muslimien asema vahvistui ja he saivat lisää arvostusta kautta koko Arabian. Sopimushetkellä muslimit eivät voineet aavistaa, että ennennäkemättömän suuri joukko ihmisiä saapuisi seuraavana vuonna Medinaan liittyäkseen muslimeihin. Ennen lähtöään paluumatkalle muslimit, Profeetan (SAWS) esimerkkiä seuraten, uhrasivat ja leikkasivat hiuksensa. Vaikka heidän päämääränsä. Pyhä Moskeija, jäikin saavuttamatta, Allah hyväksyi heidän pyhiinvaelluksensa. Olihan heidän aikomuksensa ollut puhdas ja vilpitön. Medinaan palattaessa ilmoitettiin Profeetalle (SAWS) Koraanin Voiton suura. Se alkaa seuraavasti:

Useimmat niistä, joiden sopimuksen perusteella olisi pitänyt palata Mekkaan, eivät sitä tehneet. Sensijaan he liittyivät ryhmiksi, jotka asustelivat meren rannikolla. Siellä asusteli ennestään muita Mekasta paenneita ryhmiä. Yhdessä nämä alkoivat ahdistella mekkalaisten karvaaneja ja häiritä näiden elinkeinoa. Mekkalaiset pyysivät silloin Profeettaa (SAWS) ottamaan nuo uudet muslimit luokseen Medinaan, ilman että heidän pitäisi palata Mekkaan. Rannikon nuorukaiset liittyivät Profeettaan (SAWS) ja mekkalaisten ja medinalaisten välit lientyivät. Näiden nuorukaisten jälkeen, saapuivat Abessiniassa asuneet muslimit. Tuotapikaa oli Medinan uskovaisten lukumäärä kaksinkertaistunut. Samoihin aikoihin, Khaiid ibn al-Walid, sama suuri soturi, joka oli kukistanut muslimit Uhudin taistelussa, lähti Mekasta kohti Medinaa. Matkallaan hän kohtasi 'Amr ibn al-'Asin, sen nokkelan puhujan, joka aikoinaan yritti palauttaa muslimit Abessiniasta. Hän oli itse yrittänyt asettua Abessiniaan ja oli palaamassa sieltä, sen jälkeen kun Negus oli kehoittanut häntä siirtymään islamiin. Hän kysyi Khalidilta: "Minne matka?" Tähän Khalid vastasi: "Asiat ovat kirkastuneet minulle. Se mies on todellakin Profeetta. Kautta Allahin olen matkalla tullakseni muslimiksi. En näe syytä miksi viivytellä?" 'Amr ibn al-As vastasi: "Olen samalla asialla." He jatkoivat yhdessä matkaa kohti Medinaa, liittyäkseen Profeettaan (SAWS). Toisaalta molempia miehiä huolestutti Profeetan (SAWS) tapaaminen. Olivathan he molemmat aikoinaan taistelleet muslimeita vastaan. Niinpä kun 'Amr astui Profeetan (SAWS) eteen, hän sanoi: "Oi Profeetta, saanko aiemmat rikkeeni anteeksi, eikä menneitä enää muistella?" Siihen Profeetta (SAWS) vastasi: "Hyvä 'Amr, islam pyyhkii pois kaiken menneen, kuten myös tekee Hijrah (muutto Medinaan)."

Kun vuosi Hudaybian sopimuksesta oli kulunut saattoi Profeetta (SAWS) johtaa 2000:n pyhiinvaeltajan joukon 'Umralle Mekkaan. Qureishilaiset tyhjensivät Mekan ja katselivat pyhiinvaellusmenoja ympäröiviltä kukkuloilta. Sovittua kolmen päivän aikarajaa kunnioitettiin molemmin puolin. Tämän jälkeen muslimit palasivat Medinaan.