We investigate the wage, employment and reallocation effects of the introduction of a nationwide minimum wage in Germany that affected 15% of all employees. Based on identification designs that exploit variation in exposure across individuals and local areas, we find that the minimum wage raised wages, but did not lower employment. It also led to the reallocation of low-wage workers from smaller to larger, from lower- to higher-paying, and from less- to more-productive establishments. This worker upgrading accounts for up to 17% of the wage increase induced by the minimum wage. Moreover, at the regional level, average establishment quality increased in more affected areas in the years following the introduction of the minimum wage.