Na Buzakhah zond Abu Bakr ﵁ Khalid ﵁ niet rechtstreeks terug naar Medina. Hij stuurde nieuwe orders na hem aan. Doorstoten naar de Banu Tamim in Najd, daarna Musaylimah in al-Yamamah. Een eerdere expeditie onder ʿIkrimah ibn Abi Jahl ﵁ had al een nederlaag geleden in de buurt van al-Yamamah. Een tweede onder Shurahbil ibn Hasanah ﵁ wachtte op versterking. Khalid ﵁ moest de twee samenvoegen en de slag herstellen.
De afstand van Buzakhah naar al-Yamamah is groot. Bijna vijftienhonderd kilometer over hete vlakten, langs putten die soms uitgedroogd waren. Khalid ﵁ koos voor een snelle route langs Dahna en at-Tahaluf. Hij splitste zijn leger niet en hield de cavalerie geconcentreerd. De Muhajirun en Ansar marcheerden in het centrum, de bondgenoten van de zojuist gepacificeerde Najd-stammen op de flanken.
Onderweg naderden hem verschillende delegaties van Tamim. Sajaah, de profetes uit Banu Yarbu, had haar leger gehad maar inmiddels weer ontbonden, deels omdat zij een wonderlijk verbond met Musaylimah had gesloten en daarna teruggetrokken naar Mesopotamië. Maaliek ibn Nuwayrah was in een eerder gevecht door Khalid ﵁'s mannen gedood, een zaak die later in Medina nog opnieuw geopend zou worden door ʿUmar ﵁. Khalid ﵁ bleef vooruitgaan. Zijn opdracht was duidelijk en de tijd drong.
In al-Yamamah wachtte Musaylimah met een leger van naar verluidt veertigduizend man. De Banu Hanifa was geen zwakke stam. Zij bezaten landbouwgrond, palmboomgaarden, ommuurde tuinen die als forten konden dienen. Musaylimah had hen overtuigd door middel van prozarymen die op koranische passages leken maar in inhoud betekenisloos waren. “Yaa difdaʿu, binta difdaʿayni”, “O kikker, dochter van twee kikkers.” Niemand in al-Yamamah had het hardop tegengesproken.
Toen Khalid ﵁ zich bij ʿIkrimah ﵁ en Shurahbil ﵁ aansloot, telde de Muslim-strijdmacht ongeveer dertienduizend man. Zij sloegen hun kamp op ten noorden van ʿAqraba, een vlakte ten noorden van de stad Hajr. Khalid ﵁ stuurde een verkenner. De man werd gevangen genomen en voor Musaylimah gebracht. Musaylimah liet hem in leven, gaf hem een boodschap mee en stuurde hem terug. Khalid ﵁ las de boodschap, scheurde haar in tweeën zonder een woord, en gaf het bevel om de volgende ochtend op te trekken.
In de nacht voor de slag liep Khalid ﵁ door de kampen. Bij elke vlag bleef hij staan, sprak met de bannerdrager, herinnerde hem aan een specifieke deugd van de Profeet ﷺ. Bij de vlag van de Ansar herhaalde hij de woorden uit Surah at-Tawbah over hen die geloofden, hijraf maakten en streden. Bij de vlag van de Muhajirun reciteerde Ubayy ibn Kaʿb ﵁ enkele verzen die hij van de Profeet ﷺ persoonlijk had ontvangen. Het kamp sliep weinig die nacht. Aan de horizon, boven de palmgaarden van Hajr, was de gloed van Musaylimah’s vuren te zien.