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