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