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