To many economists the public's support for the minimum wage (MW) institution is puzzling, since the MW is considered a "blunt instrument" for redistribution. To delve deeper in this issue we build models in which workers are heterogeneous in ability. In the first model, the government does not engage in any type of redistributive policies - except for the payment of unemployment benefits; we find that the MW is preferred by the majority of workers (even when the unemployed receive very generous unemployment benefits). In the second model, the government engages in redistribution through the public provision of private goods. We show that (i) the introduction of a MW can be preferred by a majority of workers only if the unemployed receive benefits which are substantially below the after-tax earnings they would have had in the perfectly competitive case, (ii) for a given generosity of the unemployment benefit scheme, the maximum, politically viable, MW is lower than in the absence of in-kind redistribution, and (iii) the MW institution is politically viable only when there is a limited degree of in-kind redistribution. These findings can possibly explain why a well-developed social safety net in Scandinavia tends to co-exist with the absence of a national MW, whereas in Southern Europe the MW institution "complements" the absence of a well-developed social safety net.