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