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