ثم ارتحل أَبُومحمد إلى المشرق, فسمعه الفرضيُّ يقول: كانَت رحْلَتي إلى المَشْرِق: في المحرَم سنة إحدى وخَمْسين وثلاثِ مائةٍ (1/ 351 هـ، وله نحو 27سنة).

فدخل مصر, ولقي فيها القاضي أبا الطاهر البغدادي، وابن رشيق، وحمزة الكناني الحافظ، وأبا إسحاق ابن شعبان، ومحمد بن عبد الله بن زكريا النيسابوري، وغيرهم.

وكان معه في الرحلة أَبُوالحسن القابسي، وأبو موسى عيسى بن سعادة (?).

ففي أول لقاء جمع هؤلاء النفر مع حمزة الكناني جرت لهم قصة، ذكرها ابن بشكوال في ترجمة عمر بن عبيد الله بن زاهر:

قال أَبُوالحسن القابسي: قال لنا حمزة بن محمد الكناني حين دخلت عليه أنا وأبو موسى عيسى بن سعادة وأبو محمد الأصيلي، ووافقناه نازلًا في الدرج، درج مسجد يقال إنه مسجد ابن لهيعة في حضرموت، فقال: من هؤلاء؟ فقيل له: قوم مغاربة، فوقف فسلمنا عليه، ثم رجع فنظر في وجوهنا وقال: ما أرى إلا خيرًا، حدثونا عن محمد بن كثير، عن سفيان الثوري، عن عمرو بن قيس الملائي، عن عطية العوفي، عن أبِي سعيد الخدري، أنَّ رسول الله صلى الله عليه وسلم قال: «إحذروا فراسة المؤمن، فإنه ينظر بنور الله»، وتلا {إِنَّ فِي ذَلِكَ لَآيَاتٍ لِلْمُتَوَسِّمِينَ}