This paper analyzes the effects of introducing a graduated minimum wage in a model with optimal income taxation in which a government seeks to maximize social welfare. It shows that the optimal graduated minimum wage increases social welfare by increasing the low-productivity workers' consumption and bringing it closer to the first-best. The paper also describes how the graduated minimum wage in a social welfare optimum depends on important economy characteristics such as the government's revenue needs, the social-welfare weight of low-productivity workers, and the numbers and productivities of the different types of workers.