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