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

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

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

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