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