خوارج، گروهی از مسلمانان بودند که از زمان آغاز خلافت اسلامی به دلیل اختلافات عقیدتی و سیاسی، همواره به ایجاد آشوب و مخالفت با حاکمان میپرداختند. در دوران عبدالملک بن مروان، این گروه نیز فعال بودند و با ایجاد ناامنی و شورش در مناطق مختلف، تهدیدی جدی برای ثبات حکومت به شمار میرفتند. از آنجا که عبدالملک در زمان حکومتش با رقیب مهمی همچون ابن زبیر در مکه روبهرو بود، خوارج که پیش از این در دوره ابن زبیر فعالیت داشتند، پس از سقوط آل زبیر نیز به شورش و تخریب ادامه دادند.
یکی از برجستهترین رهبران خوارج در این دوره، ابوفدیک بود که پس از غلبه بر نجدة بن عامر در یمامه، کنترل منطقه بحرین را به دست گرفت. عبدالملک برای مقابله با تهدید او، فرمان تشکیل سپاهی به فرماندهی عمر بن عبدالله بن معمر را صادر کرد. سپاه اعزامی شامل نیروهایی از کوفه و بصره بود و نبردی سخت میان سپاه خوارج و لشکر خلافت در گرفت. در نهایت ابوفدیک کشته شد و شورش خوارج در یمامه و بحرین سرکوب گردید، به طوری که دیگر فعالیت قابل توجهی از آنان در این مناطق دیده نشد.
در مناطق دیگر نیز، خوارج با هدایت رهبران محلی مانند قطری بن فجاءة و صالح بن مخارق به شورش ادامه میدادند. مهلب بن ابیصواری و دیگر فرماندهان خلافت مانند عبدالعزیز و عبدالرحمن بن مخنف مأمور مقابله با آنان شدند. اگرچه در برخی نبردها خوارج توانستند پیروزیهایی کوتاه به دست آورند و حتی تلفات به نیروهای خلافت وارد کردند، اما در نهایت با تلاش مهلب و سپاهش، شورشها سرکوب و خوارج در مناطق جنوب و غرب ایران کنترل شدند. شکستهای پی در پی و سرکوبهای نظامی سبب شد که قدرت خوارج در دوران عبدالملک به شدت کاهش یابد و توانایی آنها برای ایجاد بحرانهای بزرگ از میان برود.