Maka Abrahah pun menjadi gubernur koloni Aksum di wilayah Himyar Yaman, Arab Selatan. Kemudian dia menyaksikan orang-orang Arab berbondong-bondong datang ke Makkah setiap tahun untuk menunaikan ibadah haji. Maka kemudian dia membangun sebuah gereja besar dan mewah di Yaman dan menamakannya dengan Al-Qulais.
Gereja itu dibangun dari batu hijau, kuning, putih dan hitam yang dibawa dari sebuah puri yang lebih tua yang terletak di Ma'rib. Menuju ke gereja adalah tangga marmer, sedangkan pintunya terbuat dari perunggu atau tembaga. Gereja menggabungkan tiga elemen arsitektur terpisah yang dikenal sebagai bayt, iwan dan qubbah. Iwan dan qubbah, terdiri dari ornamen mosaik motif bunga dan bintang emas untuk yang pertama, dan salib mosaik polikrom, perak dan emas untuk yang terakhir. Dia bermaksud mengalihkan tujuan orang-orang Arab yang setiap tahun bepergian ke Mekah menunaikan ibadah haji untuk menuju ke gereja megah yang dibangun di Yaman.
Kejadian tersebut didengar oleh seorang laki-laki dari Bani Kinanah. Dia melakukan perjalanan menuju gereja tersebut dan memasukinya pada suatu malam, kemudian melumuri dinding-dindingnya dengan kotoran.
Abrahah yang mendengar berita tersebut marah besar dan memutuskan untuk menghancurkan Ka’bah. Dia kemudian memimpin langsung sebuah pasukan tentara yang berjumlah 60.000 dengan fasilitas pasukan yang dilengkapi oleh beberapa ekor gajah.
Ketika pasukan Abrahah sampai di Thaif, orang orang Tsaqif keluar menemui mereka karena khawatir pasukan Abrahah keliru menghancurkan kuil mereka yaitu al-Lat karena dikira Ka'bah. Mereka segera menjelaskan kepada Abrahah ia belum mencapai tujuan, orang orang Tsaqif juga bahkan memberi penunjuk jalan yaitu Abu Righal untuk mengantar pasukan Abrahah walaupun sudah mempunyai penunjuk jalan yaitu Nufayl kemudian Abrahah pun menerima tawaran tersebut. Tapi penunjuk jalan tersebut Abu Righal meninggal dalam perjalanan kira kira 2 mil sebelum Mekah, disebuah tempat bernama Mughammis dan ia dikuburkan disana. Dan sampai hari ini orang orang Arab jika melewati tempat itu selalu melempari kuburan Abu Righal tersebut dengan batu karena itu adalah kuburan dari seorang pengecut dan pengkhianat yang membantu pasukan Abrahah.
Abrahah berhenti di Mughammis dan mengirim pasukan berkuda ke daerah pinggiran Mekah dan merampas harta harta berharga yang ditemukan diperjalanan termasuk 200 ekor unta milik Abdul Muthalib. Kaum Qurays dan suku suku lainya disekitar Mekah mengadakan pertemuan dewan perang, mereka memutuskan percuma saja mereka melawan pasukan Abrahah yang sangat kuat tersebut, sementara itu Abrahah mengirim seorang utusan ke Mekah dan menyampaikan pesan dari Abrahah bahwa pasukanya datang hanya untuk menghancurkan Ka'bah dan jika ingin menghindari pertumpahan darah maka pimpinan kota Mekah harus datang ke Mughammis dan menemui Abrahah di kemahnya.
Hal tersebut menyebabkan Abdul Muththalib yang pada waktu itu menjadi tokoh masyarakat Quraisy datang menemui Abrahah. Begitu Abrahah melihat Abdul Muththalib, dia memberikan penghormatan dan memuliakannya.
Tatkala Abrahah bertanya apa maksud kedatangannya, dia berkata, “Maksud kedatangan saya adalah berharap Raja mengembalikan unta-unta saya yang ditawan.”
Abrahah berkata, “Semula saya kagum kepadamu saat melihat kedatanganmu, kemudian saya tidak lagi menghargaimu setelah kamu berbicara kepadaku. Apakah kamu hanya memikirkan untamu dan sama sekali tidak membicarakan tentang Ka’bah yang merupakan agamamu dan agama leluhurmu, padahal kedatanganku kemari adalah untuk menghancurkannya?”
Abdul Muththalib berkata, “Saya adalah pemilik unta-unta itu. Adapun Ka’bah, maka Pemiliknyalah yang akan menjaganya.”
Abrahah berkata, “Tidak akan ada yang mampu mencegah saya.”
Abdul Muththalib berkata, “Itu urusan kamu dan Pemiliknya” (maksud pemilik Ka’bah adalah Allah Ta’ala). "kita lihat saja nanti" ujarnya dan berkata lagi "kembalikan unta unta ku sekarang" dan Abrahah pun memerintahkan kepada pasukanya agar mengembalikan unta unta milik Abdul Muthalib.
Abdul Muthalib kembali ke Mekah bersama 200 ekor untanya dan menyarankan agar orang orang Mekah menyelamatkan diri ke atas bukit bukit dekat kota Mekah, kemudian ia ditemani beberapa anggota keluarganya dan beberapa pemuka Qurays pergi ke Ka'bah dan berdiri di sisi Ka'bah dan Abdul Muthalib sambil memegang cincin besi di pintu Ka'bah memohon "Ya Allah hamba hamba Mu melindungi rumahnya, maka lindungila rumah Mu ini", Setelah berdoa maka mereka berjalan menuju bukit bukit di sekitar kota Mekah, ribuan orang-orang Quraisy yang lainya mengungsi keluar berlindung ke gunung gunung dan menanti sambil melihat apa yang akan dilakukan oleh tentara Abrahah.
Abrahah mempersiapkan pasukannya untuk melanjutkan perjalanan menuju Mekah, tatkala pasukan memerintahkan gajah yang bernama Mahmud itu untuk berjalan menuju Mekah, ternyata gajah tersebut duduk (tidak mau jalan). Mereka akhirnya memaksanya dengan memukulinya, tetapi dia tetap enggan untuk berjalan. Namun, ketika mereka mengarahkan ke arah selain Makkah ternyata gajah itu mau berjalan.
Tiba tiba langit di ufuk barat menghitam pekat dan suara suara gemuruh menggelegar muncul gelombang kegelapan yang menyapu dari arah laut dan menutupi langit diatas mereka, sejauh jangakauan pandangan mereka melihat langit dipenuhi beribu ribu burung yang tak terhingga jumlahnya. Orang orang yang berhasil selamat menceritakan bahwa burung burung tersebut terbang secepat burung layang layang dan masing masing membawa 3 batu kecil yang membara, satu di paruhnya dan yang lain dicengkram oleh ke dua kakinya. Burung burung itu menukik ke arah pasukan Abrahah sambil menjatuhkan batu batu yang mereka bawa yang meluncur dengan cepat menembus setiap pasukan dan membuat mereka terkapar dan membusuk, ada yang membusuk dengan cepat dan ada juga yang perlahan, puluhan ribu pasukan Abrahah pada hari itu menjadi bangkai. Mereka lari kocar-kacir mencari jalan keluar dan tempat untuk berlindung. Dan raja Abrahah sendiri mendapat luka di tubuhnya, kemudian ia dilarikan menjauh dari Mekah oleh anak buahnya. Namun anggota tubuh Abrahah terus berjatuhan satu demi satu dan ia pun meninggal dunia saat tiba di San’a dengan kondisi dada dan hatinya terpisah.Tidak semua pasukan terbunuh dan sebagian besar pasukan tersebut kembali ke Shan'a dalam keadaan kacau dan kebanyakan mati dalam perjalanan pulang ke Shan'a.
Sejak peristiwa itu Qurays dikenal di jazirah Arab dengan sebutan "Keluarga Tuhan", dan Qurays semakin dikagumi karena Tuhan mengabulkan doa doa mereka untuk melindungi Ka'bah dari serbuan puluhan ribu pasukan bergajah pimpinan Abrahah.
“Apakah kamu tidak memperhatikan bagaimana Tuhanmu telah bertindak terhadap tentara bergajah? Bukankah Dia telah menjadikan tipu daya mereka (untuk menghancurkan Ka’bah) itu sia-sia? Dan Dia mengirimkan kapada mereka burung yang berbondong-bondong, yang melempari mereka dengan batu (berasal) dari tanah yang terbakar, lalu Dia menjadikan mereka seperti daun-daun yang dimakan (ulat).” (QS. Al-Fil: 1-5).
Peristiwa kehancuran pasukan bergajah di pinggiran Mekah terjadi pada bulan Muharram bertepatan dengan akhir Februari atau awal bulan Maret tahun 571 Miladiyah, atau sekitar dua bulan sebelum kelahiran Nabi Saw. Gereja al qalis itu dikatakan telah bertahan setidaknya sampai masa pemerintahan khalifah Abbasiyah al-Mansur 714-775 M.