كانت نجران ولاية تابعة للدولة الرومانية ، يحكمها أسقف من قِبل هرقل مع رؤساء قبائلها ، والمشهور فيهم بنو عبد المدان . وكان ارتباطهم بهرقل وثيقاً فهو يدافع عنهم وينفق عليهم ، وقد بعث لهم بصليب كبير من ذهب .

وفى نجران كانت قصة أصحاب الأخدود التي ذكرها الله تعالى في سورة البروج فقال : وَالسَّمَاءِ ذَاتِ الْبُرُوجِ . وَالْيوْمِ الْمَوْعُودِ . وَشَاهِدٍ وَمَشْهُودٍ . قُتِلَ أَصْحَابُ الآخْدُودِ . النَّارِ ذَاتِ الْوَقُودِ . إِذْ هُمْ عَلَيهَا قُعُودٌ . وَهُمْ عَلَى مَا يفْعَلُونَ بِالْمُؤْمِنِينَ شُهُودٌ .

قال القمي في تفسيره : ٢ / ٤١٣ : « كان سببهم أن الذي هيج الحبشة على غزو اليمن ذو نواس ، وهو آخر من ملك من حمير ، تهوَّد واجتمعت معه حمير على اليهودية وسمى نفسه يوسف ، وأقام على ذلك حيناً من الدهر ، ثم أُخبر أن بنجران بقايا قوم على دين النصرانية ، وكانوا على دين عيسى وعلى حكم الإنجيل ، ورأس ذلك الدين عبد الله بن بريا ، فحمله أهل دينه على أن يسير إليهم ويحملهم على اليهودية ويدخلهم فيها ، فسار حتى قدم نجران فجمع من كان بها على دين النصرانية ثم عرض عليهم دين اليهودية والدخول فيها فأبوا عليه ، فجادلهم وعرض عليهم وحرص الحرص كله ، فأبوا عليه وامتنعوا من اليهودية والدخول فيها واختاروا القتل ، فخد لهم أخدوداً جمع فيه الحطب وأشعل فيه النار ، فمنهم