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