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