يقول عدي وهو يحكي قصة ذهابه إلى المدينة:

ما رجل من العرب كان أشد كراهة لرسول الله - صلى الله عليه وسلم - مني ..

وكنت على دين النصرانية ..

وكنت ملكاً في قومي لما كان يصنع بي.

فلما سمعت برسول الله - صلى الله عليه وسلم - كرهته كراهية شديدة ..

فخرجت حتى قدمت الروم على قيصر ..

قال: فكرهت مكاني ذلك ..

فقلت: والله لو أتيت هذا الرجل .. فإن كان كاذباً لم يضرني .. وإن كان صادقاً علمت ..

فقدمت فأتيته .. فلما دخلت المدينة جعل الناس يقولون: هذا عدي بن حاتم .. هذا عدي بن حاتم ..

فمشيت حتى أتيت فدخلت على رسول الله - صلى الله عليه وسلم - في المسجد فقال لي: عدي بن حاتم؟

قلت: عدي بن حاتم ..

فرح النبي - صلى الله عليه وسلم - بمقدمه .. واحتفى به .. مع أن عدياً محارب للمسلمين وفارٌ من الحرب .. ومبغض للإسلام .. ولاجئٌ إلى النصارى .. ومع ذلك لقيه - صلى الله عليه وسلم - بالبشاشة والبشر .. وأخذ بيده يسوقه معه إلى بيته ..

عدي وهو يمشي بجانب النبي - صلى الله عليه وسلم - يرى أن الرأسين متساويان .. !!

فمحمد (- صلى الله عليه وسلم -) ملك على المدينة وما حولها .. وعدي ملك على جبال طي وما حولها ..

ومحمد (- صلى الله عليه وسلم -) على دين سماوي " الإسلام " .. وعدي على دين سماوي " النصرانية " ..

ومحمد (- صلى الله عليه وسلم -) عنده كتاب منزل " القرآن " .. وعدي عنده كتاب منزل " الإنجيل " ..

كان عدي يشعر أنه لا فرق بينهما إلا في القوة والجيش ..

في أثناء الطريق وقعت ثلاثة مواقف: