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