Lịch sử ban đầu của Mecca không được ghi chép đầy đủ, ^[7] với tài liệu tham khảo phi Hồi giáo đầu tiên xuất hiện vào năm 741 CN, sau cái chếtcủa Nhà tiên tri Muhammad , trong Biên niên sử Byzantine-Ả Rập.Nguồn này xác định nhầm vị trí Mecca ở Mesopotamia thay vì vùng Hejaz phía tây Ả Rập, nơi khan hiếm nguồn khảo cổ và văn bản.^{[số 8]}Mặt khác, Medina đã có người ở ít nhất từ ​​thế kỷ thứ 9 trước Công nguyên.^[9] Vào thế kỷ thứ 4 CN, đây là quê hương của các bộ lạc Ả Rập từ Yemen và ba bộ lạc Do Thái: Banu Qaynuqa, Banu Qurayza và Banu Nadir.^[10]Muhammad , Nhà tiên tri của đạo Hồi, sinh ra ở Mecca vào khoảng năm 570 CN và bắt đầu chức vụ ở đó vào năm 610 CN.Ông di cư đến Medina vào năm 622 CN, nơi ông thống nhất các bộ lạc Ả Rập theo đạo Hồi.Sau cái chết của ông vào năm 632 CN, Abu Bakr trở thành vị vua đầu tiên, kế vị là Umar, Uthman ibn al-Affan và Ali ibn Abi Talib.Thời kỳ này đánh dấu sự hình thành của Rashidun Caliphate .Dưới thời Rashidun và sau đó là Umayyad Caliphate , người Hồi giáo đã mở rộng lãnh thổ của họ một cách đáng kể, từ Bán đảo Iberia đến Ấn Độ.Họ đã đánh bại quân đội Byzantine và lật đổ Đế chế Ba Tư , chuyển trọng tâm chính trị của thế giới Hồi giáo sang những vùng lãnh thổ mới giành được này.Bất chấp những mở rộng này, Mecca và Medina vẫn là trung tâm của tâm linh Hồi giáo.Kinh Qur'an quy định tất cả những người Hồi giáo có khả năng phải hành hương đến Mecca.Masjid al-Haram ở Mecca, cùng với Kaaba, và Masjid al-Nabawi ở Medina, có lăng mộ của Muhammad, là những địa điểm hành hương quan trọng kể từ thế kỷ thứ 7.^[11]Sau sự sụp đổ của Đế chế Umayyad vào năm 750 CN, khu vực sau này trở thành Ả Rập Xê Út phần lớn quay trở lại chế độ quản lý bộ lạc truyền thống, vẫn tồn tại sau những cuộc chinh phục đầu tiên của người Hồi giáo.Khu vực này được đặc trưng bởi bối cảnh biến động của các bộ lạc, các tiểu vương quốc bộ lạc và các liên minh, thường thiếu sự ổn định lâu dài.^[12]Muawiyah I, vị vua Umayyad đầu tiên và là người gốc Mecca, đã đầu tư vào quê hương của mình bằng cách xây dựng các tòa nhà và giếng nước.^[13] Trong thời kỳ Marwanid, Mecca phát triển thành một trung tâm văn hóa cho các nhà thơ và nhạc sĩ.Mặc dù vậy, Medina vẫn có tầm quan trọng lớn hơn trong phần lớn thời kỳ Umayyad, vì đây là nơi cư trú của tầng lớp quý tộc Hồi giáo đang phát triển.^[13]Triều đại của Yazid tôi đã chứng kiến ​​tình trạng hỗn loạn đáng kể.Cuộc nổi dậy của Abd Allah bin al-Zubair dẫn đến việc quân đội Syria tiến vào Mecca.Thời kỳ này chứng kiến ​​một trận hỏa hoạn thảm khốc làm hư hỏng Kaaba, được Ibn al-Zubair sau đó xây dựng lại.^[13] Năm 747, một phiến quân Kharidjit từ Yemen đã chiếm giữ Mecca trong một thời gian ngắn mà không gặp phải sự kháng cự nào nhưng nhanh chóng bị Marwan II lật đổ.^[13] Cuối cùng, vào năm 750, quyền kiểm soát Mecca và vương quốc lớn hơn được chuyển giao cho nhà Abbasids.^[13]