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