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