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