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