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