وقال: "أغر، بسم الله، وفي سبيل الله، فقاتل من كفر بالله، ولا تغدر، ولا تقتل وليدا، وبعثه إلى كلب بدومة الجندل، وقال: إن استجابوا لك فتزوج، ابنة ملكهم".

فسار عبد الرحمن حتى قدم دومة الجندل، فمكث ثلاثة أيام يدعوهم إلى الإسلام، فأسلم الأصبغ بن عمرو الكلبي، وكان نصرانيا، وكان رئيسهم، وأسلم معه ناس كثير من قومه، وأقام من أقام على إعطاء الجزية.

وتزوج عبد الرحمن تماضر -بضم المثناة الفوقية، وكسر الضاد المعجمة- بنت الأصبغ، وقدم بها المدينة