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