We study a search model with employment protection legislation. We show that if the output from the match is uncertain ex ante, there may exist a discriminatory equilibrium where workers with the same productive characteristics are subject to different hiring standards. If a bad match takes place, discriminated workers will use longer time to find another job, prolonging the costly period for the firm. This makes it less profitable for the firms to hire the discriminated workers, thus sustaining discrimination. In contrast to standard models, the existence of employers with a taste for discrimination may make it more profitable to discriminate also for firms without discriminatory preferences.