Ka’bah awalnya dibangun oleh Adam dan kemudian anak Adam, Syist, melanjutkannya. Saat terjadi banjir Nabi Nuh, Ka’bah ikut musnah dan Allah memerintahkan Nabi Ibrahim membangun kembali. Al-Hafiz Imaduddin Ibnu Katsir mencatat riwayat itu berasal dari ahli kitab (Bani Israil), bukan dari Nabi Muhammad.
Ka’bah yang dibangun Ibrahim pernah rusak pada masa kekuasaan Kabilah Amaliq. Ka’bah dibangun kembali sesuai rancangan yang dibuat Ibrahim tanpa ada penambahan ataupun pengurangan. Saat dikuasai Kabilah Jurhum, Ka’bah juga mengalami kerusakan dan dibangun kembali dengan meninggikan fondasi. Pintu dibuat berdaun dua dan dikunci.
Di masa Qusai bin Kilab, Hajar Aswad sempat hilang diambil oleh anak-anak Mudhar bin Nizar dan ditanam di sebuah bukit. Qusai adalah orang pertama dari bangsa Quraisy yang mengelola Ka’bah selepas Nabi Ibrahim. Di masa Qusai ini, tinggi Ka’bah ditambah menjadi 25 hasta dan diberi atap. Setelah Hajar Aswad ditemukan, kemudian disimpan oleh Qusai, hingga masa Ka’bah dikuasai oleh Quraisy pada masa Nabi Muhammad.
Dari masa Nabi Ibrahim hingga ke bangsa Quraisy terhitung ada 2.645 tahun. Pada masa Quraisy, ada perempuan yang membakar kemenyan untuk mengharumkan Ka’bah. Kiswah Ka’bah pun terbakar karenanya sehingga juga merusak bangunan Ka’bah. Kemudian, terjadi pula banjir yang juga menambah kerusakan Ka’bah. Peristiwa kebakaran ini yang diduga membuat warna Hajar Aswad yang semula putih permukaannya menjadi hitam.
Untuk membangun kembali Ka’bah, bangsa Quraisy membeli kayu bekas kapal yang terdampar di pelabuhan Jeddah, kapal milik bangsa Rum. Kayu kapal itu kemudian digunakan untuk atap Ka’bah dan tiga pilar Ka’bah. Pilar Ka’bah dari kayu kapal ini tercatat dipakai hingga 65 H. Potongan pilarnya tersimpan juga di museum.
Empat puluh sembilan tahun sepeninggal Nabi (yang wafat pada 632 Masehi atau tahun 11 Hijriah), Ka’bah juga terbakar. Kejadiannya saat tentara dari Syam menyerbu Makkah pada 681 Masehi, yaitu di masa penguasa Abdullah bin Az-Zubair, cucu Abu Bakar, yang berarti juga keponakan Aisyah.
Untuk membangun kembali, seperti masa-masa sebelumnya, Ka’bah diruntuhkan terlebih dulu. Abdullah AzZubair membangun Ka’bah dengan dua pintu. Satu pintu dekat Hajar Aswad, satu pintu lagi dekat sudut Rukun Yamani, lurus dengan pintu dekat Hajar Aswad. Abdullah bin Az-Zubair memasang pecahan Hajar Aswad itu dengan diberi penahan perak. Yang terpasang sekarang adalah delapan pecahan kecil Hajar Aswad bercampur dengan bahan lilin, kasturi, dan ambar. Jumlah pecahan Hajar Aswad diperkirakan mencapai 50 butir.
Pada 693 Masehi, Hajjaj bin Yusuf Ath-Taqafi berkirim surat ke Khalifah Abdul Malik bin Marwan (khalifah kelima dari Bani Umayyah yang mulai menjadi khalifah pada 692 Masehi), memberitahukan bahwa Abdullah bin Az-Zubair membuat dua pintu untuk Ka’bah dan memasukkan Hijir Ismail ke dalam bangunan Ka’bah.
Hajjaj ingin mengembalikan Ka’bah seperti di masa Quraisy; satu pintu dan Hijir Ismail berada di luar bangunan Ka’bah. Maka, oleh Hajjaj, pintu kedua–yang berada di sebelah barat dekat Rukun Yamani–ditutup kembali dan Hijir Ismail dikembalikan seperti semula, yakni berada di luar bangunan Ka’bah.
Akan tetapi, Khalifah Abdul Malik belakangan menyesal setelah mengetahui Ka’bah di masa Abdullah bin AzZubair dibangun berdasarkan hadis riwayat Aisyah. Di masa berikutnya, Khalifah Harun Al-Rasyid hendak mengembalikan bangunan Ka’bah serupa dengan yang dibangun Abdullah bin Az-Zubair karena sesuai dengan keinginan Nabi.
Namun, Imam Malik menasihatinya agar tidak menjadikan Ka’bah sebagai bangunan yang selalu diubah sesuai kehendak setiap pemimpin. Jika itu terjadi, menurut Imam Malik, akan hilang kehebatannya di hati kaum Mukmin.
Pada 1630 Masehi, Ka’bah rusak akibat diterjang banjir. Sultan Murad Khan IV membangun kembali, sesuai bangunan Hajjaj bin Yusuf hingga bertahan 400 tahun lamanya pada masa pemerintahan Sultan Abdul Abdul Aziz. Sultan inilah yang memulai proyek pertama pelebaran Masjidil Haram.