When Abu Bakr ﵁ appointed the eleven brigades for the war against the apostates, the heaviest front fell to Khalid ibn al-Walid ﵁. His orders were clear. March into Najd, break Tulayha before his movement could reach Medina, and then push on to the Banu Tamim and al-Yamamah.
The jama’a in Medina was exhausted. Many had returned from the failed expedition under ʿUsamah ibn Zayd ﵁, others were still on their way back from Syria. Khalid ﵁ set out nonetheless with a core force and received reinforcements along the way. He followed the old Najd route the Prophet ﷺ had once described, past wells and oases that every trader from Mecca knew.
At Dhul-Qassa, two days’ journey from Medina, Khalid ﵁ had his men make camp. He sent scouts ahead and waited for news of Tulayha’s position. The false claimant had established himself at Buzakhah, a well deep in Najd, and the Ghatafan under ʿUyaynah ibn Hisn had gone over to him. Together they formed the greatest threat in the southern Najd.
Khalid ﵁ chose a swift approach. A long siege would give other tribes time to pick a side. He ordered a forced march, leaving the women and children behind at Dhul-Qassa, and sent a vanguard ahead to scout the outer picket posts of Tulayha’s camp.
In Medina, Abu Bakr ﵁ received reports of Khalid ﵁'s progress. The khalifah stood on the minbar of the Prophet ﷺ and reminded the people of the words of Allah: “And those who turn away after him — Allah will bring a people whom He loves and who love Him.” For many in Medina this was no war against a foreign enemy. It was the first time the Sahabah ﵃ drew weapons against Arabs who had spoken the shahadah but refused the zakat.
The advance itself took less than two weeks. Khalid ﵁ kept discipline strict. No plundering on the way. No mercy for those who had tried to murder the zakat collectors. The tribes between Medina and Buzakhah who wavered were offered a return to Islam without retribution over the zakat itself. Many accepted. The army grew.
By the time Khalid ﵁ neared Buzakhah, his strength had doubled. The Najd lay open before him. But Tulayha knew he was coming, and he had made preparations of his own.