دعا رسولُ الله صلَّى اللهُ عليه وسلَّم عبدَ الرَّحمنِ بنَ عوفٍ رَضي اللهُ عنه، فقال له: "تَجهَّزْ؛ فإنِّي باعِثُك في سَريَّةٍ مِن يَومِك هذا، أو مِن الغَدِ إن شاءَ اللهُ تعالى"، فأصبَحَ عبدُ الرَّحمنِ فغَدا إلى رسولِ الله صلَّى اللهُ عليه وسلَّم، فأقعَدَه بين يَدَيه وعمَّمَه بيَدِهِ، ثمَّ عَقَد له رسولُ الله صلَّى اللهُ عليه وسلَّم اللواءَ بيَدِه، أو أمرَ بلالًا يَدفَعُه إليه، ثم قال له: "خُذه باسمِ اللهِ وبَرَكَتِه"، ثم حَمِد الله تعالى، ثم قال صلَّى اللهُ عليه وسلَّم: "اغزُ باسمِ الله، وفي سَبيلِ الله، فقاتِل مَن كَفَر بالله! ولا تَغُلَّ -الغُلولُ: هو الخيانةُ في المَغنَمِ والسَّرِقةُ من الغَنيمةِ قَبْلَ القِسمةِ-، ولا تَغدِرْ، ولا تَقتُلْ وَليدًا"، ثم أمَرَه رسولُ الله أن يَسيرَ إلى بني كَلْبٍ بدُومةِ الجَندَلِ، فيَدعوَهم إلى الإسلامِ، وقال له: "إنِ استَجابوا لَكَ فتَزَوَّجِ ابنةَ مَلِكِهِم". فسار عبدُ الرَّحمنِ رَضي اللهُ عنه بأصحابِه وكانوا سَبعَمِئةِ رَجلٍ، حتى قَدِمَ دُومةَ الجَندَلِ؛ فمَكَث ثلاثةَ أيَّامٍ يَدعوهم إلى الإسلامِ؛ فلمَّا كان اليومُ الثالِثُ أسلَمَ رأسُهم ومَلِكُهمُ الأصبَغُ بنُ عَمرٍو الكَلبيُّ، وكان نَصرانيًّا، وأسلَمَ معه ناسٌ كَثيرٌ من قَومِه؛ فبَعَث عبدُ الرحمنِ رافِعَ بنَ مَكيثٍ بَشيرًا إلى النبيِّ صلَّى اللهُ عليه وسلَّم يُخبِرُه بما فَتَح الله عليه وكَتَب له بذلك، وتزوَّجَ عبدُ الرحمنِ تُماضِرَ بِنتَ الأصبَغِ وقَدِمَ بها المدينةَ، فوَلَدَت له بعد ذلك أبا سَلَمةَ بنَ عبدِ الرَّحمنِ بنَ عَوفٍ.