Employers’ access to and use of criminal records as a selection mechanism in the labor market makes it far more difficult for ex-offenders to find jobs, especially regular, well-paid jobs, than those without criminal convictions. The paper asks whether there is anything morally problematic about this practice. The aims of the paper are twofold. First, arguments based on premises of wrongful discrimination against the current, commonest use of criminal records are critically discussed. It is argued that employers do not necessarily engage in morally wrongful discrimination against job applicants when they use criminal records in recruitment screening, but it is also argued that ex-offenders who apply for jobs are subject to what can be called “structural and morally wrongful discrimination” when laws allow employers to request (or directly access) a job applicant’s full criminal record. Second, preliminary proposals on how criminal records can be used by employers in a way that avoids wrongful structural discrimination of ex-offenders will be presented and critically assessed. I suggest that it should be lawful for an employer to access an applicant’s criminal records only where there is a relevant and special match or link between the crime on the records and the job being applied for and the crime is serious. This proposal is defended against two objections, one based on concerns about crime prevention and the other based on the employer’s interest in knowing whom not to hire.