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