The decline of employment-based health plans is commonly attributed to rising premium costs. Using restricted data and a matched sample from the Medical Expenditure Panel Survey–Insurance Component, the authors extend previous studies by testing the relationships among premium costs, employment relationships, and the provision of health benefits between 1999 and 2012. The authors report that both establishment- and state-level union densities are associated with a higher likelihood of employers’ providing health plans, whereas right-to-work legislation is associated with lower provision. These factors combined rival rising premium cost in predicting offering. This finding indicates that the declining provision of health benefits could be in part driven by the transformation of the employment relationship in the United States and that labor unions may remain a critical force in sustaining employment-based coverage in the twenty-first century.