Новым главой мусульманской общины был избран ближайший сподвижник Мухаммеда — Абу Бакр. Его назвали «заместитель посланника Аллаха» — халифа расули-л-лах, или проще — халиф.
Абу Бакр не имел такого безусловного авторитета, как Мухаммед. Раньше конфликты среди мусульман решались легко: достаточно было слова пророка. Теперь приходилось полагаться только на себя. Права любого правителя могли быть подвергнуты сомнению — ведь он не пророк Аллаха. Новых же пророков, по учению ислама, больше быть не могло. Поэтому по-настоящему нового вождя признали только в Медине. Другие арабские племена считали, что принесли присягу самому Мухаммеду, а раз он умер, они больше никому ничего не должны. Мухаммед был посланник Божий, а кто такой Абу Бакр? «Мы рабы Аллаха, а не Абу Бакра», — говорили бедуины.
Начался процесс, который в арабской истории называют ридда: массовое отпадение племен от ислама и отказ платить положенную дань — садаку. Для многих именно вопрос садаки был ключевым: они соглашались принять новую религию, если это им ничего не стоило. Несколько племен предложили халифу договор, по которому они обязались и дальше признавать ислам, но без уплаты дани. Но Абу Бакр прекрасно понимал решающее значение денег — именно они были фактическим выражением власти. Он ответил: «Без садаки нет ислама».
В конце концов, Аравию пришлось завоевывать заново. Мусульманское ядро в Медине должно было на деле доказывать свои права на власть. И оно стало делать это всеми доступными способами, от прямой военной силы до подкупов и убийств. Решающую роль в победе мусульман сыграл Халид аль-Валид. Его почтительно называли Сайфуллах — «меч Аллаха». Вместе со своей армией он прошел по всей Аравии, убеждая бедуинов железом и пламенем, что ислам — это истинная религия и садаку лучше платить. Но сами мусульмане относились к нему неоднозначно. Говорили, что Халид проливал кровь мусульман. Однажды, возвращаясь в Медину, он вез с собой знатного пленника, вождя племени бан йараб по имени Малик и его красивую жену. Ночью во время привала Малик был убит. Почему это произошло, точно неизвестно: рассказывали и о случайной ошибке (якобы Халид приказал обогреть пленников, а слугам послышалось слово «убить»), и о грубых словах, за которые поплатился Малик. Зато достоверно известно, что вскоре Халид женился на вдове убитого.
Разобравшись с восточной угрозой, Халид отправился на запад, в Йамаму, и напал на последнего из оставшихся лжепророков Мусайлиму. Сторонники Мусайлимы показали себя храбрыми бойцами и в кровопролитной битве все пали на поле боя вместе со своим предводителем. Мусульмане тоже понесли сильный ущерб: многие видные сподвижники Мухаммеда были убиты, а Халид ранен. Но это не помешало женолюбивому военачальнику сразу после боя справить свадьбу с дочерью одного из захваченных в плен врагов.