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