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