ثم بعث رسول الله - صلى الله عليه وسلم - خالد بن الوليد في ربيع الآخر سنة 10 هـ إلى بني عبد المدان بنجران من أرض اليمن ليدعوهم إلى الإسلام ثلاثة أيام، فإن أبوا قاتلهم، فلما قدم إليهم بعث الركبان في كل وجه، يدعون إلى الإسلام، وكتب بذلك إلى رسول الله - صلى الله عليه وسلم -، فأرسل إليه أن يقدم بوفدهم ففعل، ولما اجتمعوا به - صلى الله عليه وسلم - قال لهم: بم كنتم تغلبون من قاتلكم في الجاهلية؟ قالوا: كنا نجتمع ولا نتفرق، ولا نبدأ أحدًا بظلم، قال: صدقتم، وأمر عليهم قيس بن الحصين. ورجعوا إلى قومهم في بقية شوال أو صدر ذي القعدة. ثم أرسل إليهم عمرو بن حزم ليفقههم في الدين، ويعلمهم السنة ومعالم الإسلام، ويأخذ منهم صدقاتهم وكتب له كتابًا. وهو كتاب مشهور جدًا.

وهي أيضًا قبيلة يمانية، أرسل إليهم رسول الله - صلى الله عليه وسلم - علي بن أبي طالب في رمضان سنة 10 هـ ليدعوهم إلى الإسلام، وأمره أن لا يقاتلهم حتى يقاتلوه، فلما انتهى إليهم، ولقي جموعهم دعاهم إلى الإسلام، فأبوا ورموا المسلمين بالنبل، فصف على مع أصحابه، وقاتلهم حتى هزمهم، فكف عن طلبهم قليلًا، ثم لحقهم ودعاهم إلى الإسلام فأسلموا، وبايعه رؤساؤهم، وقالوا: نحن على من وراءنا من قومنا، وهذه صدقاتنا، فخذ منها حق الله، ففعل، ثم رجع إلى رسول الله - صلى الله عليه وسلم - فوافاه بمكة في حجة الوداع.

هي أيضًا قبيلة مشهورة في جهة اليمن، توافدوا برئاسة صرد بن عبدالله الأزدي، فأسلموا، فأمره عليهم، وأمره أن يجاهد بمن أسلم من يليه من أهل الشرك.