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