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