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