Как и в Мекке, в Наджране была Кааба. Возможно, изначально речь шла о святилище, месте паломничества в дохристианские времена. В поздний доисламский период это слово использовалось для обозначения большой церкви, кафедрального собора епископа. Его описывают как великолепное сооружение, украшенное мраморами и мозаиками, подаренными византийским императором. В этом нет ничего невероятного. Византийское правительство всегда было озабочено созданием «сфер влияния» в Западной Аравии, а мозаики, как известно, были среди даров, которые отправлялись потенциальным друзьям Византии. Поэтому в «Сире» говорится, что в Наджране была религия «царя», то есть византийского императора. Нет никаких сомнений в том, что Наджран был монофизитским. Строгая ортодоксия Византии едва ли применялась в отношениях с городом, который ей был так нужен в качестве противовеса персидскому влиянию в Аравии. Определенно епископ Абу-Харита принадлежал к племени бакр, бывшему монофизитским. Самый известный епископ Аравии позднего доисламского периода был Косс ибн Саида. Его имя традиционно связывали с Наджраном. Фр. Ламменс убедительно доказал, что эта связь ни на чем не основана. Ранние авторы ничего не знали о нем и его городе. Вокруг епископа собиралась свита священнослужителей и монахов, которые, вероятно, делали все от них зависящее, чтобы познакомить арабов с христианскими институтами. Наджран был местом, где проводились важные ежегодные ярмарки. Возможно, именно там христиане устанавливали связи с арабами-язычниками.
Наджран оставался христианским городом и в мусульманские времена до тех пор, пока его жители не были изгнаны халифом Умаром. Большинство изгнанников отправились в Ирак и там основали колонию, названную тоже Наджран. После изгнания жителей важность города стала быстро уменьшаться, и торговля перешла в Сааду.
В Наджране была иудейская колония. Очевидно, она наслаждалась терпимостью и свободой при триумвирате, но, согласно традиции, так было не всегда. Самый известный случай, связанный с историей Наджрана, – мученичество святого Арефы и его сподвижников. Она традиционно ассоциируется с арабским вождем по имени Зу Нувас, который, как утверждают, являлся прозелитом, который преследовал христиан и напал на Наджран, потому что это был христианский центр. Арефа был сеййидом Наджрана и каким-то образом также являлся агентом абиссинского правительства или был в союзе с ним. Абиссиния в то время была защитницей христианства. Поздние историки называют его абиссинским правителем. Абиссинцы уже начали проникать в Южную Аравию, и, вполне возможно, движение Зу Нуваса являлось национальным восстанием против абиссинского влияния, хотя оно в конечном счете привело к абиссинскому завоеванию. Говорят, что после захвата города Зу Нувас дал христианам выбор: отступничество или смерть. Он выкопал ров, где развел огонь, в котором сжигал всех, кто остался тверд в вере. Предполагается, что к этому эпизоду относятся слова Корана (85: 4–8): «Гибель ископавшим ров. Разжигавшим в нем огонь, поддерживавшим его растопкою! Вот, они сидели при нем. И сами были свидетелями тому, что делали верующим. Они мучили их только за то, что веровали они в Бога сильного, славного». Но некоторые комментаторы считают, что это относится к Ветхому Завету и рассказу об отроках «в пещи огненной», приведенному в Книге пророка Даниила.