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