We build a theoretical model to study whether a minimum wage can be welfare-improving if it is implemented in conjunction with an optimized nonlinear income tax. We consider this issue in a framework where search frictions on the labor market generate unemployment. Workers differ in productivity. The government does not observe workers’ productivity but only their wages. Hence, the redistributive policy solves an adverse selection problem. We show that a minimum wage is optimal if the bargaining power of the workers is relatively low. However, if the government controls the bargaining power, then it is preferable to set a sufficiently high bargaining power.