بالزحف على المهدية مركز الدولة الجديد. وجمع حوله جيشًا كبيرًا من الأعراب، إلا أن تميمًا بادره قبل أن يصل إلى المهدية، وتمكن من صد هجومه والقضاء على جيشه.
ولقد كان العدو الخارجي متربصًا مستغلاًّ لفرط الضعف, ففي سنة ٤٨٠ هـ استغل النصارى خروج تميم من المهدية لقمع بعض الثوار فهاجموها من البحر. وتمكنوا من السيطرة عليها. ولما بلغ الخبر تميمًا رجع إلى المهدية وبذل أموالًا طائلة للنصارى مقابل خروجهم منها.
وفي سنة ٤٨٤ استولى النصارى على صقلية بعدما بقيت في أيدي المسلمين مائتين ونيفا وسبعين سنة.
وبقيت أحوال تميم بن المعز معتلة وأموره متدهورة إلى أن توفي سنة ٥٠١ هـ، وتولى بعده يحيي بن تميم. وفي عهد هذا دخل محمد بن تومرت المهدية، متظاهرًا بالأمر بالمعروف والنهي عن المنكر. ثم رحل إلى المنستر ثم إلى بجاية. ولما توفي يحيي سنة ٥٠٩ هـ تولى بعده ابنه أبو الحسن علي بن يحيي باتفاق من الجند. ودخل في حروب مع الأعراب كأبيه وجده. واستمر حكمه إلى سنة ٥١٥ هـ حيث توفي وتولى بعده ابنه الحسن بن علي الذي كان عمره لا يتعدى اثني عشر عامًا.
فقصده صاحب صقلية سنة ٥١٧ هـ بأسطول ضخم ولما وصل المهدية هاج البحر ودمر سفنهم، وتعقبهم المسلمون بالقتل وغنم المسلمون غنائم كثيرة. إلا أن هذا الطاغية عاود الكرة مرة ثانية، واستولى على جربة وسفاقص وطرابلس. وفي سنة ٥٤٣ هـ باغت أهل المهدية، وأخذ أهلها على حين غفلة منهم. ففر منها الحسن بما خف حمله ودخلها النصارى من غير قتال. واستولوا على ذخائر الحسن. ثم انطلقوا نحو سوسة وسفاقص ودانت لهم سائر البلاد. أما الحسن فقد التجأ إلى عبد المؤمن بن علي الكومي مستنجدًا به ومستجيرًا، فأكرمه وأحسن وفادته، وهب لنصرته، فاتجه بنفسه سنة ٥٥٤ هـ ومعه الحسن بن علي في جيش جرار لم تشهد المنطقة مثله، وحاصر المهدية ستة أشهر وفتحها بكرة عاشوراء سنة ٥٥٥ هـ، وهي التي