The discussion of cross-deputization (mandating that police officers enforce immigration policies) is often framed as a referendum on civil rights and racial politics. Those who oppose cross-deputization often maintain that asking police to target individuals based on their immigration status endangers civil rights. Those who support cross-deputization, on the other hand, argue that enforcing immigration laws is necessary to maintain a culture of lawfulness and to preserve public safety. Previous research on the psychology of legitimacy and procedural justice, however, suggests that this is likely a false dichotomy (e.g., Alpert & Dunham, 2004; Jost & Major, 2001; Tyler & Huo, 2002), a perspective we adopt in this article. Drawing on the psychological literature on legitimacy and on our own research in the area of policing and immigration, we find that ensuring civil rights—and the perception of police fairness—does not conflict with public safety in either perception or reality. Rather, the public's belief in the fairness of law enforcement is a necessary precondition of public safety and lawfulness. In other words, because law enforcement requires legitimacy to be effective, wide-ranging concerns about racism actually become a threat to public safety. Implications for public policy are discussed.