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