Online extremists’ use of social media poses a new form of threat to the general public. These extremists range from cyberbullies to terrorist organizations. Social media providers often suspend the extremists’ accounts in response to user complaints. However, extremist users can simply create new accounts and continue their activities. In this work we present a new set of operational capabilities to address the threat posed by online extremists in social networks. We use thousands of Twitter accounts related to the Islamic State in Iraq and Syria (ISIS) to develop behavioral models for these users—in particular, what their accounts look like and with whom they connect. We use these models to track existing extremist users by identifying pairs of accounts belonging to the same user. We then present a model for efficiently searching the social network to find suspended users’ new accounts based on a variant of the classic Pólya’s urn setup. We find a simple characterization of the optimal search policy for this model under fairly general conditions. Our urn model and main theoretical results generalize easily to search problems in other fields.