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