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