A criminal record can severely damage labor market prospects. While public and private organizations have developed a host of policies to encourage employers to hire people with a record, research suggests some of the policies may have negative unintended consequences. To explore ways to mitigate these consequences, we conducted a discrete-choice experiment in the summer of 2017 with a nationally representative sample of employers. Employers indicated their preferences for incentives offered by staffing agencies to hire individuals with one non-violent felony conviction. These incentives include: a replacement guarantee, more detailed work history, provision of transportation to/from job site, and a fee discount. The baseline incentive involved a staffing agency verifying that the ex-offender did not have safety or rule violations in previous companies and a fee discount worth the same amount as the federal Work Opportunity Tax Credit for ex-felons (WOTC). At baseline, less than half (43%) of employers would consider hiring an individual with this incentive. The likelihood of hiring an individual with a record increased from the baseline by 69 percent if a staffing agency also provided a guarantee of a replacement worker in the event the individual was deemed unsuitable. Employers were 53 percent more likely to hire an individual providing a certificate of validated positive previous work performance history. Having consistent transportation increased the probability of being considered for hire by 33 percent, and doubling the fee discount increased the baseline probability by 42 percent.