واستنفر العرب ومن حوله من أهل البوادي ليخرجوا معه، فأبطأ كثير من الأعراب، أما هو فغسل ثيابه، وركب ناقته القَصْواء، واستخلف على المدينة ابن أم مكتوم أو نُمَيْلَة الليثي‏.‏ وخرج منها يوم الإثنين غرة ذي القعدة سنة 6 هـ، ومعه زوجته أم سلمة، في ألف وأربعمائة، ويقال‏:‏ ألف وخمسمائة، ولم يخرج معه بسلاح، إلا سلاح المسافر‏:‏ السيوف في القُرُب‏.‏