Учитывая роль и место племен Наджранского края в межплеменной структуре и торговле Йемена, и Аравии в целом, и желая, чтобы йеменцы Наджрана и Тихамы обрели, и как можно скоро, новую веру, Пророк послал в Северный Йемен, в августе 631 г., отряд мусульман. Состоял он из 400 воинов, во главе с легендарным военачальником Халидом ибн ал-Валидом, по прозвищу Меч Аллаха.
И повелел ему Посланник Аллаха, повествуют сказания йеменцев, явившись в земли племен бану ‘абд ал-мадан и бану ал-харис ибн каб, призвать их к исламу, и если не откажутся они от идолов-истуканов своих, то «показать им силу».Добравшись до тех мест, Халид разослал всадников-глашатаев во все концы тамошнего края. Не обошлось без стычек. Но миссия
Халида возымела успех. Ислам племена те приняли, и поклялись в верности Пророку. Направили в этих целях делегации в Медину, в январе 632 г. Сопровождал их в той поездке возвращавшийся домой Халид ибн ал-Валид. Главой мусульманской уммы
племени ал-мадан Пророк назначил Кайса ибн ал-Хусайна. Через какое-то время Пророк отправил к ним ‘Амра ибн Хазму, поручив ему наставлять людей тех в вопросах новой веры, ислама, и собирать с них установленный закат (налог на имущество и доходы).В декабре 631 г. к Пророку Мухаммаду пожаловала делегация племени бану хаулан, входившего в конфедерацию племен Северного Йемена ал-мазхидж.
Племя это жительствовало между Сана’а’ и Ма’рибом, и славилось во всей Аравии изготовлением верблюжьих седел хаулани. Основное ядро мазхиджитов, как известили Пророка посланцы, не изъявило готовности и желания обратиться в ислам. И тогда Пророк направил к ним ‘Али ибн Абу Талиба, одного из первых мусульман, своего двоюродного брата, зятя и будущего четвертого «праведного» халифа (656–661), с отрядом из 300 всадников. Велел ‘Али призвать их к исламу, но не «вынимать из ножен мечи» до тех пор, пока сами они не нападут на мусульман. На соответствующее обращение к ним ‘Али мазхиджиты, обитатели гор и долин вокруг Сана’а’, ответили отказом, сразу и решительно. Более того, обстреляли мусульман стрелами из луков. Вот тогда-то ‘Али и обрушился на них. Мазхиджитов разбил. Взял пленных из числа знатных лиц. Захватил много скота, и двинулся в глубь их удела. На пути его встало племя бану зубайд, военный кулак мазхиджитов. Предложение ‘Али принять ислам они отклонили. Произошла сшибка. Мазхиджиты были сломлены и побеждены. И только после этого, «увидев силу меча мусульман и узрев их готовность прийти на помощь друг другу», мазхиджиты решили примкнуть к ним, и согласились выплачивать закат. Некоторое время спустя делегация бану зубайд посетила Медину и присягнула на верность Пророку Мухаммаду. Вслед за ними явилась в Медину и делегация племени бану мурад (во главе с Фарвой ибн Мусайкой), другой крупной ветви бану мазхидж.Али возвратился в Медину из похода в Йемен до прощального паломничества Пророка Мухаммада. Йеменцы его полюбили.
Будучи человеком среднего роста, с большими черными глазами и густой длинной бородой, он походил на них по характеру и нраву. Они восхищались его благородством, мужеством и отвагой на поле боя, великодушием и справедливостью по отношению к поверженным им племенам.
Крупнейшие конфедерации племен Горного Йемена, ал-бакил и ал-хашид, сменить веру предков не захотели
.> так же, как и племена, обитавшие в районе Адена. К первым из них в июне-июле 631 г. Пророк Мухаммад отрядил Абу Мусу ал-Аш’ари, а ко вторым – Му’аза ибн Джабали, который побывал также и в Таизе. Делегируя их с миссией в Йемен, Пророк Мухаммад наставлял обоих своих посланцев остерегаться забирать что-либо у тех, кто «уверует в Аллаха и согласится выплачивать закат с их имущества на нужды бедных из их же числа», и особенно то, что «наиболее дорого им». Давал наказ, чтобы от мужчины, который отступится от мусульманства, они требовали, чтобы он вернулся в ислам. И если отступник покается и сделает это, то не трогали бы его, а оставляли в общине (умме). Но вот если он не откликнется на призыв их, то тогда бы рубили ему голову, без жалости и сожаления. Известно, что Абу Муса ал-Аш’ари возвратился в Медину перед прощальным паломничеством Пророка.