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