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

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

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