This paper provides the first systematic study of how minimum wage policies in China affect firm employment over the 2000-2007 periods. Using a novel dataset of minimum wage regulations across more than 2,800 counties matched with firm-level data, we investigate both the effect of the minimum wage and its policy enforcement tightening in 2004. A dynamic panel (difference GMM) estimator is combined with a "neighbor-pairs-approach" to control for unobservable heterogeneity common to "border counties" that are subject to different minimum wage changes. We show that minimum wage increases have a significant negative impact on employment, with an estimated elasticity of -0.1. Furthermore, we find a heterogeneous effect of the minimum wage on employment which depends on the firm's wage level. Specifically, the minimum wage has a greater negative impact on employment in low-wage firms than in high-wage firms. Our results are robust for different treatment groups, sample attrition correction, and placebo tests.