Войско Усамы отдохнуло и было готово к новым сражениям. Из всех бойцов, имевшихся в его распоряжении, Абу Бакр составил 11 боевых отрядов. Командиры этих отрядов получили разгромить вероотспутников и восстановить единство мусульманского государства.
Сам Абу Бакр во главе отдельного отряда выступил против племен Абс и Зубьян, которые населяли Аль-Абрак, и нанес им поражение в Рабзе. Затем он отправился в местечко Бузаха для приведения к покорности остававшихся там представителей этих племен; там же находился и лжепророк Тулайха. Тем временем, выполняя приказ халифа, полководец Халид ибн аль-Валид вошел в область, где проживало племя Тай. Ади ибн Хатим, вождь этого племени, попросил у Халида три дня, чтобы привести свой народ к покорности, и действительно выполнил намерение - племя Тай полностью покорилось Халиду ибн аль-Валиду.
После этого он двинулся в направлении Бузахи, где, понеся потери, разгромил враждебное племя Фазара во главе с Уйайной ибн Хусном. Самому Уйайне удалось бежать; бежал в Сирию и лжепророк Тулайха. Тулайха отступил от веры и выступил против мусульман еще при жизни пророка Мухаммада, который посылал против него войска во главе с Дарраром ибн аль-Азваром.
Вероотступники бежали в Сухайру и не могли оказать сопротивление, но после смерти пророка они усилились. Племя Гатафан поддержало асадитов, к которым принадлежал и Тулайха; они заключили союз с племенем Тай. Когда асадиты стали союзниками гатафанцев, Даррар не сумел удержать ситуацию под контролем и бежал в Медину, а его войска разошлись. Когда же Халид ибн аль-Валид привел к покорности племена в Бузахе, асадиты, амириты и гатафанцы снова вернулись к Исламу.
Завершив свою миссию в этом районе, Халид ибн аль-Валид по приказу халифа двинулся в Битах против одной из ветвей племени Тамим, которое называлось Бану Йарбу. Их возглавлял Малик ибн Нувайра.
Внутри племени Тамим были раздоры, и они подверглись нападению отряда под командованием женщины по имени Саджах из племени Бану Таглиб. Части тамимитов удалось договориться с ней, а остальные бежали. Потом Саджах двинулась на Йамаму, где находился лжепророк Мусайлима со своими сторонниками. Там они пришли к согласию и даже поженились, но были вместе лишь 3 дня; затем Саджах вернулась к своему племени и, подобно Мусайлиме, объявила себя пророчицей. Ее поддержали некоторые из тамимитов, и она заключила мир с Мусайлимой при условии, что ей будет принадлежать половина доходов Йамамы. Затем она вернулась к себе; однако к тому времени мусульмане установили контроль над ее территориями, и Саджах приняла Ислам. Когда она вновь вернулась в Аравию, в среде тамимитов возникли разногласия, и они не захотели вновь подчиниться этой женщине. Спустя некоторое время сюда вошла армия Халида ибн аль-Валида; он схватил вождей тамимитов и, обнаружив, что они правили одной из ветвей этого племени Бану Йарбук, не обладая на это правами, казнил их.
Икрима ибн Абу Джахль получил приказ наказать лжепророка Мусайлиму и направился в Йамаму; за ним следовал Шурахбил ибн Хасана. Икрима вступил в сражение с силами племени Бану Ханифа, к которому принадлежал Мусайлима, но потерпел поражение; Шурахбил же решил подождать подкрепления. В это время Абу Бакр послал Икриме приказ после завершения карательной операции против мятежников двинуться на вероотступников в Омане и соединиться там с силами Хузайфы ибн Мухсина и Арфаджи ибн Харсамы. Затем они должны были соединиться с войсками Мухаджира ибн Абу Умаййи, которому было предписано завершить операцию в Йемене и подойти к ним со стороны Хадрамаута. Тем временем Халид ибн аль-Валид вернулся в Медину и попросил у Абу Бакра прощения за ошибки, допущенные им в прошлом походе. Тот хорошо принял и выслушал его, а затем приказал срочно выступить против лжепророка Мусайлимы. Халид сразу выехал к своим войскам в Битах, дождался подхода подкреплений и выступил против Мусайлимы. Войдя в Йамаму, он обнаружил, что Шурахбил ибн Хасана, прибывший туда ранее, внезапно, не дождавшись подкрепления, перешел в наступление и потерпел поражение.
В племени Бану Ханифа, с которым сразился Шурахбил, была небольшая группа, которая оставалась верной Исламу и помогала мусульманам; их возглавлял Салама ибн Асал. Лжепророк Мусайлима, собрав свои силы, перешел в наступление на мусульман со стороны Акрабы и Джубайла (ныне Вади Ханифа). В ответ Халид начал контрнаступление. Правым и левым флангами армии мусульман командовали Зейд ибн аль-Хаттаб (брат Омара ибн аль-Хаттаба) и Абу Хазайфа ибн Утба. Знаменосцем мухаджиров был вольноотпущенник Абу Хузайфы Салим, а ансаров - Сабит ибн Кайс ибн Шаммас. С севера, со стороны Малхама, к Акрабе подошел Даррар ибн аль-Азвар. Вначале вероотступники значительно потеснили мусульман, но затем последние перехватили инициативу и нанесли поражение противнику. Мусайлима с группой приверженцев попытался скрыться, но ему это не удалось, и все они были убиты; однако и мусульмане понесли большие потери. В этой битве пали смертью мучеников многие видные деятели Ислама - Зейд ибн аль-Хаттаб, Сабит ибн Кайс и др.
В Омане Лакиту ибн Малику аль-Йазди также удалось потеснить мусульман. Находившиеся здесь мусульманские войска под командованием Джафара и Убада были вынуждены отступить в горы и на побережье. Джафар обратился к Абу Бакру с просьбой о помощи, и тот отправил в Оман Хузайфу ибн Мухсина, а в Махру - Афраджу ибн Харсаму, которые должны были начать в Омане военные действия и встретиться с войсками Джафара и Убада. Туда же был послан Икрима ибн Абу Джахль, потерпевший поражение в Йамаме и просивший халифа отправить его в Оман.
Получив приказ халифа, Икрима поспешил за Хузайфой и Афраджой и догнал их еще до того, как они вошли в Оман. Там они соединились с войсками Джафара и Убада, составили план совместных действий и подошли к местности Саххар. Их противники под командованием Лакита сосредоточились в Дабе, и там начались ожесточенные сражения. Положение мусульман было настолько сложным, что если бы к ним на помощь не подоспели подкрепления из Бахрейна и других регионов, то они были бы разгромлены; однако в конце концов мусульмане победили и захватили много трофеев, пятую часть которых отправили в государственную казну.
Хузайфа остался в Омане для управления этой областью. Икрима же вернулся в Махру. Жители Махры тоже отступили от Ислама, но разделились на две части. Меньшая часть, которую возглавлял Шихрит, располагалась на побережье. Икрима начал с них. Прежде всего он предложил им обратиться в Ислам, и многие из них приняли это предложение, оставшаяся же часть вероотступников после этого оказалась обессиленной. Они объединились вокруг некоего Мусбиха, но в кратчайшие сроки были разгромлены. Пятую часть трофеев, добытых в результате этой победы, Икрима отправил с Шихритом в Медину.
В Йемене, как и в других регионах, каждая область имела своего вождя. Как уже было сказано, там еще при жизни пророка Мухаммада объявил себя пророком некий аль-Асвад аль-Анси. Против него выступили мусульмане во главе с персом Файрузом ад-Дайлами и убили его. Однако в связи с тем, что спустя один день умер пророк Мухаммад, йеменцы отказались подчиниться мусульманскому государству. Назначенные пророком наместники Амр ибн Хазм и Халид ибн Саид ибн аль-Ас были вынуждены вернуться в Медину. Тогда халиф Абу Бакр начал принимать меры. Прежде всего он попытался разрешить конфликт мирным путем и предложил йеменцам принять Ислам и прекратить сопротивление, а затем был вынужден отправить наместника Мекки Аттаба ибн Усайда и его брата Халида ибн Усайда в йеменскую область Тихаму, чтобы покарать вероотступников. Этот поход был успешным, и противник был разгромлен. В Таиф был послан Осман ибн Абуль-Ас, а в Шунуу - Ибн Рабиа. Жители этих областей также были усмирены.
Затем в Тихаме взбунтовались племена Ук и Ашар. Против них двинулся Тахир ибн Абу Хала, и ему удалось добиться успеха. После этого Абу Бакр послал Тахира ибн Абу Халу на помощь мусульманам Саны, а Абдулла ибн Саур получил приказ мобилизовать войска. Кроме того, Абу Бакр отправил в Йемен Мухаджира ибн Абу Умаййу и Халида ибн Усаййида. По мере продвижения по мекканской дороге к ним присоединялись другие отряды. Этот поход был успешным - мусульманам удалось разгромить йеменских вероотступников и пленить их лидеров Амра ибн Маадикариба и Кайса ибн Ади Йагуса аль-Макшуха, которые были отправлены к Абу Бакру.
