Miscreants register thousands of new domains every day to launch Internet-scale attacks, such as spam, phishing, and drive-by downloads. Quickly and accurately determining a domain's reputation (association with malicious activity) provides a powerful tool for mitigating threats and protecting users. Yet, existing domain reputation systems work by observing domain use (e.g., lookup patterns, content hosted)-often too late to prevent miscreants from reaping benefits of the attacks that they launch. As a complement to these systems, we explore the extent to which features evident at domain registration indicate a domain's subsequent use for malicious activity. We develop PREDATOR, an approach that uses only time-of-registration features to establish domain reputation. We base its design on the intuition that miscreants need to obtain many domains to ensure profitability and attack agility, leading to abnormal registration behaviors (e.g., burst registrations, textually similar names). We evaluate PREDATOR using registration logs of second-level.com and.net domains over five months. PREDATOR achieves a 70% detection rate with a false positive rate of 0.35%, thus making it an effective- and early-first line of defense against the misuse of DNS domains. It predicts malicious domains when they are registered, which is typically days or weeks earlier than existing DNS blacklists.