After years of stagnation, labeling theory has recently gained new empirical support. Simultaneously, new policy initiatives have attempted to restructure criminal record stigma to reduce reintegration barriers, and subsequent recidivism, driven by labeling. For example, in a recent Department of Justice (DOJ) language policy, person‐first terms (e.g., “person with a conviction”) were substituted for crime‐first terms (e.g., “offender”). The Equal Employment Opportunity Commission has also issued guidelines to structure how decision‐makers use criminal records. Unfortunately, little is currently known about the social construction and use of criminal record stigma or the potential effects of such policy changes. In the current study, we provide two unique empirical tests. In study 1, we examine the social construction of stigma by testing DOJ's language policy with experimental data from a nationally representative sample of American adults (N = 996). In study 2, we use a separate nationwide experiment (N = 1,540) to examine how the contextualization of criminal records influences social exclusion decisions. Across both studies, we find consistent evidence of a “mark of violence.” The public perceives that individuals with violent convictions are the most likely to commit future crimes, and it is more supportive of excluding these individuals from employment. Crime‐first terms exacerbate perceived recidivism risk for individuals with violent convictions.