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