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

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

ويروى أنه قال له هذا ما قال لك عمرو : سيأتيك فى حفش أمك. فقال له قرة : يا أبا سليمان ، إنى قد أجرته فأحسنت جواره ، وأنا مسلم لم ارتد ، فقال : لو لا ما تذكر لضربت عنقك ، ولكن لا بد أن أبعث بك فى وثاق إلى أبى بكر فيرى فيك رأيه ، فلما فرغ من بيعة بنى عامر أوثق عيينة بن حصن ، وقرة بن هبيرة ، وبعث بهما إلى أبى بكر الصديق.

قال ابن عباس : فقدم بهما المدينة فى وثاق ، فنظرت إلى عيينة مجموعة يداه إلى عنقه بحبل ينخسه غلمان المدينة بالجريد ، ويضربونه ، ويقولون : أى عدو الله ، أكفرت بالله بعد إيمانك؟ فيقول : والله ما كنت آمنت بالله.