In this paper, we show that firm heterogeneity and labor market sorting can help us understand a number of empirical facts, and aspects related to the political economy of minimum wages. We study a competitive economy with non-transferable utility, and preferences which depend on worker and firm types. Sorting in this environment can be induced by complementarities in productions or forces related to preferences. With firm heterogeneity, minimum wage increases affect workers above the minimum wage threshold, reducing wage inequality, increasing dispersion in firm profits and reducing the size of employment effects. It can also explain why such policies have political support, as workers above the threshold benefit from the policy.