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