ولكن سرعان ما استعادها المرابطون في أواخر سنة 509 هـ وعينوا عليها واليًا جديدًا هو أنور بن أبي بكر اللمتوني، فأضحت بذلك الجزائر الشرقية جزءًا من الدولة المرابطية الكبرى ودخلت في عهد جديد من تاريخها، سيما بعد تعيين محمد بن غانية المسوفي واليًا عليها سنة 520 هـ، من قبل الأمير علي بن يوسف. واستطال حكمه لتلك الجزائر زهاء ثلاثين عامًا، أي إلى مابعد سقوط الدولة المرابطية في المغرب والأندلس. وعمل على توطيد سلطانه هناك والاستقلال بشؤونها وجعل منها ملجأً ومثوى للوافدين والفارين من فلول لمتونة أمام الموحدين. وبعد وفاته سنة 550 هـ خلفه على ولاية ميورقة ابنه عبد الملك الذي لم تطل ولايته إذ خلفه أخوه إسحاق بن محمد حتى تاريخ وفاته سنة 579 هـ. ووليها ابنه عبد الله منذ سنة 583هـ حتى سنة 600 هـ تاريخ افتتاحها من طرف الموحدين.
وكان الفتح الموحدي لميورقة ضربة شديدة لبني غانية، قضت نهائيًا على سلطانهم في الجزائر الشرقية، وكان لهذا الفتح وقع عميق أيضًا لدى الممالك النصرانية القريبة، سيما مملكة أرجوان في شرق شبه الجزيرة، وهذا ما تشير إليه رسالة الفتح التي بعثها الخليفة الناصر من إنشاء كاتبه ابن عياش حين تقول:"ولأخذ ميورقة على صاحب أراغونه وبرشلونة أشد من شرق النبل، وأهول من وقع السيف، وأوحش من القطع بحلول الممات" [1] . وكان أول الولاة الموحدين على ميورقة هو أبو محمد عبد الله بن طاع الله الكومي، ثم ولى الناصر عليها عمه السيد أبا زيد بن أبي يعقوب يوسف وندب ابن طاع الله لقيادة البحر، وبعده وليها السيد أبو عبد الله بن أبي حفص عمر بن عبد المؤمن [2] . أما رابع الولاة الموحّدين عليها فهو الذي أخذها منه النصارى، وبه استهل ابن عُميرة المخزومي حديثه في مخطوط تاريخ ميورقة موضوع هذا البحث.
(1) مجموع رسائل موحدية (الرسالة السادسة والثثون) ، ليفي بروفنسال، ص 68.
(2) كتاب العبر، مصدر سابق، مج6، ص 292.