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

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

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