قررت قريش أن تتبع المسلمين في الحبشة، ولما كانت قريش لا تستطيع أن تهاجم الحبشة بجيش؛ لأنها مملكة قوية على مسافة بعيدة، بالإضافة إلى العلاقات الطيبة بين الحبشة ومكة، فبحثت قريش عن حل لا يدفع للقتال، فقررت أن ترسل وفداً يطلب من ملك الحبشة أن يرد المسلمين إليها، يعني: لجأت إلى المفاوضات السياسية بينها وبين ملك الحبشة، والمهمة صعبة؛ لأن ملك الحبشة مشتهر بين الناس أنه لا يظلم عنده أحد، مما يجعل المهمة تحتاج إلى احتيال كبير، فحاولت قريش بكل طاقتها أن تنجح هذه المهمة، فاختارت على رأس الوفد اثنين من أمكر رجال قريش: عمرو بن العاص وعبد الله بن أبي ربيعة وهذان أسلما بعد ذلك، لكن إسلامهما كان متأخراً.
كان عمرو بن العاص مشهوراً بالدهاء والمكر، ويستطيع بذكائه -بحسابات قريش- أن يتصرف مع ملك الحبشة، ليس هذا فحسب، بل هو صديق شخصي له، وفوق كل هذا فأخو عمرو بن العاص وهو هشام بن العاص كان ضمن المهاجرين إلى الحبشة، فالأمر بالنسبة لـ عمرو يعتبر قضية شخصية، وأيضاً مهمة رسمية، وأيضاً أخو عبد الله بن ربيعة عباس بن أبي ربيعة رضي الله عنهما كان من المهاجرين، فاختاروا هذين الرجلين ليقوما بهذه المهمة في منتهى الجدية، وأنفقوا كثيراً على هذه السفارة: {إِنَّ الَّذِينَ كَفَرُوا يُنْفِقُونَ أَمْوَالَهُمْ لِيَصُدُّوا عَنْ سَبِيلِ اللَّهِ} [الأنفال:36]، حملَّت قريش الوفد بالهدايا الثمينة وبالذات الجلود، وهذا نوع من الرشوة للملك ولرجال الحكم في الحبشة.
كان عمرو بن العاص في منتهى الذكاء، فلم يدخل على النجاشي مباشرة، إنما ذهب في البداية إلى البطارقة، وهم يمثلون كبار رجال الحكم والدين الموجودين تحت النجاشي في الحبشة، وحمَّلهم جميعاً بالهدايا العظيمة، وبهذا ضمن وقوفهم معه ضد المسلمين، وتأثيرهم على النجاشي.