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