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