We study how lack of information on the skills of workers affects both employers and job seekers. To do so, we design and implement a field experiment in the Ugandan labor market: through the provision of certifications, we vary whether new information on the soft skills of workers is disclosed to both managers and workers during job interviews. We show that both sides of the market react to the information: managers of higher ability update their beliefs on worker’s skills, while workers with higher skills revise their outside options upwards. Guided by these facts, we develop a screening model with two-sided updating. The model predicts non-monotonic impacts of the certifications on job offers and hires along the distribution of soft skills, due to differential effects on worker’s outside options. In line with these predictions, we find the largest employment gains for workers in the middle of the skill distribution. Our estimates of the Internal Rate of Return (IRR) of the intervention range between 9-29%, implying positive net gains for the average participant. Motivated by the heterogeneous impacts on workers, we use the model to determine the cost-effectiveness of introducing a mandatory certification policy on soft skills along the entire skill distribution.