Bullying is a significant school problem. Policies have been developed to reduce bullying, yet little is known about their implementation, which must occur for these policies to have an effect. This study examines associations between the overall implementation of a state anti-bullying policy and implementation of specific components outlined in the policy with two outcomes: bullying among students and teacher protection of students. Data were collected from 588 educators in K-12 schools across North Carolina a year following the enactment of an anti-bullying law in the state. Results show that overall policy implementation fidelity is inversely related to student bullying and positively related to teacher protection. In addition, the implementation of certain policy components (i.e., educator and student knowledge of bullying reporting procedures, training of educators about protected classes from bullying, student knowledge of protected classes, and educators reporting and remediating bullying based on protected classes) is significantly related to the outcomes. Thus, the implementation of certain anti-bullying policy components may be more potent in addressing bullying. Future research should identify constellations of policy strategies that need to be activated in schools to eliminate bullying.