The introduction of a federal minimum wage in Germany in 2015 created a profound wage shock on the labor market. We exploit the variation of this treatment across regions and different employees to estimate its impact on labor earnings and employment. The main contribution of this paper is to break down the effect heterogeneity for different degrees of labor substitutability. We use data on job content as well as survey information on the workplace to approximate substitutability of labor with capital. Although the federal minimum had a substantial impact on affected wages, a significant impact on employment cannot be identified for the average employee with various identification strategies. Yet, when the treatment is interacted with the substitutability of labor, we find statistically significant negative effects on the probability of remaining employed and a significantly higher unemployment risk for those employees who are more easily replaced by capital as production factor. We find this pattern to be consistent for alternative measures of substitutability as well as alternative specifications of the model. The fact that employers seem to cut primarily replaceable jobs provides valuable insights for targeted policies supporting those employees with the highest labor market risks following the introduction (or increase) of a minimum wage.