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