In 625 verbande de profeet Mohammed de Joodse stam Banu Nadir uit Medina (in Saudi-Arabië). Zij vestigden zich in de nabijgelegen oase Khaybar, maar wilden terug naar Medina. Twee jaar later, in 627, belegerden zij samen met inwoners van Mekka en bedoeïenen de stad, die in handen was van Mohammed en zijn volgelingen. Zij verloren de strijd. Voor straf belegerde het leger van Mohammed in Khaybar een Joodse stam die tegen hem had meegevochten. Nadat zij zich hadden overgegeven, richtte het leger een groot bloedbad aan onder de mannen van die stam. Sindsdien wordt bij anti-Joodse rellen nog steeds geroepen: “Khaybar Khaybar, o Joden, het leger van Mohammed komt eraan.”
In ca. 644 bepaalde de kalief Omar dat alle Joden en christenen moesten verdwijnen uit het Arabisch schiereiland (behalve Jemen) om dit te zuiveren van andersgelovigen. Kalief Omar legde tussen 717-720 het fundament voor het dhimmi-statuut. Joden en christenen kregen de status van ‘dhimmi’, tweederangsburgers. Voor dhimmi’s gelden beperkende maatregelen in het uitoefenen van geloof, zij moesten kenmerkende kleding dragen en extra belastingen betalen.