قال ابن الكلبي كان أبوه من أهل اليمن فسقط إلى مكة فولد له بها كلدة وعبد الرحمن وكانا ملازمين لصفوان بن أُمَيَّة بن خلف الجمحي.
وذكر ابن سَعْد، عَن الواقدي أن عبد الرحمن كان أسود.
وقال ابن أبي خيثمة، عَن مصعب الزبيري كانا أخوى صفوان لأمه أمهم صفية بنت معمر بن حبيب بن وهب بن حذافة بن جمح قال العلائي، عَن مصعب الزبيري كان كلدة وعبد الرحمن من مسلمة الفتح. انتهى.
وقصة كلدة مع صفوان بن أُمَيَّة لما انهزم المسلمون يوم حنين مشهورة وقد قال القدامي في فتوح الشام إن عبد الرحمن شهد فتح دمشق وإن خالد بن الوليد بعثه إلى أبي بكر يبشره بيوم أجنادين.