لما عاد صلاحُ الدين إلى مصرَ بلَغَه أنَّ باليمن إنسانًا يسمَّى عبدَ النبي بن مهدي صاحِبَ زبيد يزعُمُ أنه ينتشر ملكُه حتى يملِكَ الأرضَ كُلَّها، وكان قد ملك كثيرًا من بلادِ اليمَنِ, واستولى على حصونِها وخطب لنَفسِه، وقطع الخطبةَ للخليفةِ العباسي, وكان السُّلطانُ قد ثبتت قواعِدُه وقَوِيَ عسكرُه، فاستأذن السلطان نور الدين محمود في أن يسيرَ إلى اليمن لقصدِ عبد النبي، فأذِنَ له في ذلك، فجهَّز أخاه شمس الدولة توران شاه بجيش اختاره، وتوجَّه إليها من الديار المصرية في مستهَلِّ رجب، فوصل إلى مكَّةَ، ومنها إلى زبيد، وفيها صاحِبُها المتغَلِّبُ عليها المعروفُ بعبد النبي، فلما قرُبَ منها رآه أهلُها، فاستقَلُّوا من معه، فقاتلهم شمس الدولة ومن معه، فلم يثبُت أهلُ زبيد وانهزموا، ووصل المصريونَ إلى سور زبيد، فلم يجدوا عليه من يمنَعُهم، فنصبوا السلالم، وصَعَدوا السور، فملكوا البلدَ عَنوةً ونَهَبوه وأكثروا النَّهبَ، وأخذوا عبد النبيِّ أسيرًا وزوجتَه المدعوة بالحُرَّة، وسَلَّمَ شمسُ الدولة عبد النبي إلى أحد أمرائه، يقال له سيف الدولة مبارك بن كامل من بني منقذ، أصحاب شيزر، وأمره أن يستخرجَ منه الأموالَ، وبذلك انتهت الدولة المهديَّة باليمن، ولَمَّا ملكوا زبيدَ واستقَرَّ الأمر لهم بها ودان أهلُها، وأقيمت فيها الخُطبةُ العباسيَّة، أصلحوا حالها، وساروا إلى عدن، وصاحِبُها ياسرُ بنُ بلال، فسار إليهم وقاتَلَهم، فانهزم ياسِرٌ ومن معه، وسبقهم بعضُ عسكر شمس الدولة، فدخلوا البلدَ قبل أهله، فملكوه، وأخذوا صاحِبَه ياسرًا أسيرًا، وأرادوا نهبَ البلد، فمنعهم شمسُ الدولة، وقال: ما جئنا لنخربَ البلاد، وإنما جئنا لنَملِكَها ونُعَمِّرَها وننتفع بدخلها؛ فلم ينهب منها أحدٌ شيئًا، فبقيت على حالها وثبَت مُلكُه واستقَرَّ أمرُه، وبذلك انتهت دولة بني زريع في اليمن، وآل الزريع هم أهل عدن، وهم شيعةٌ إسماعيليَّةٌ من همذان بن جشم، ولَمَّا فرغ شمس الدولة مِن أمْرِ عدن عاد إلى زبيد، وملك أيضًا قلعة التعكر والجند وغيرها من المعاقل والحصون، واستناب بعدن عزَّ الدين عثمان بن الزنجيلي، وبزبيد سيفَ الدولة مبارك بن منقذ، وجعَلَ في كل قلعةٍ نائبًا من أصحابه، وألقى مُلكُهم باليمن جِرانَه ودام، وأحسَنَ شمسُ الدولة إلى أهالي البلاد، واستصفى طاعتَهم بالعدل والإحسان، وعادت زبيد إلى أحسنِ أحوالها من العمارة والأمن.