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

ورووا نص كتابه ٦ إلى أسقف نجران :

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

والأسقف كلمة معربة من أبيسكوبوس اليونانية ومعناها الناظر ، وكان الأسقف الشخص الأول والباقون دون رتبته ، وهو أبو حارثة بن علقمة .

فلما قرأ الأسقف الكتاب فزع وارتاع وقام وقعد ، وشاور أهل الحجى والرأي منهم ، فقال شرحبيل وكان ذا لب ورأي بنجران : قد علمت ما وعد الله إبراهيم في ذرية إسماعيل