В месяце раби‘ ас-сани 10 года Хиджры посланник Аллаха, да благословит его Аллах и приветствует, отправил Халида ибн аль-Валида к людям из племени бану Абд аль-Мадан, обитавшим в Наджране, повелев ему призывать их к Исламу в течение трёх дней, а потом вступить с ними в бой, если они откажутся.
Прибыв на место, Халид разослал всадников во все концы, и они стали призывать этих людей к Исламу и говорить им: «Примите Ислам, и вы спасётесь!» И они приняли Ислам, после чего Халид прожил среди них некоторое время, обучая их установлениям этой религии и сообщив обо всём посланнику Аллаха, да благословит его Аллах и приветствует, который велел отправить в Медину делегацию от этого племени, что и было сделано.
Когда их представители встретились с Пророком, да благословит его Аллах и приветствует, он, да благословит его Аллах и приветствует, спросил их: «Благодаря чему вы побеждали тех, кто сражался с вами во времена джахилиййи?» Они ответили: «Мы собирались воедино, а не разделялись, и мы никого не притесняли, если не притесняли нас».
Посланник Аллаха, да благословит его Аллах и приветствует, сказал: «Вы сказали правду» и назначил их правителем Кайса ибн аль-Хусайна, после чего в конце шавваля или начале месяца зу-ль-ка‘да они вернулись домой.
А через некоторое время Пророк, да благословит его Аллах и приветствует, направил к ним Амра ибн Хазма, поручив ему наставлять этих людей в религии и собирать с них установленный закят.