Background and Objectives: Warfarin and a skeletal muscle relaxant are co-treatments in nearly a quarter-million annual United States (US) office visits. Despite international calls to minimize patient harm arising from anticoagulant drug interactions, scant data exist on clinical outcomes in real-world populations. We examined effects of concomitant use of warfarin and individual muscle relaxants on rates of hospitalization for thromboembolism among economically disadvantaged persons. Materials and Methods: Using 1999–2012 administrative data of four US state Medicaid programs, we conducted 16 retrospective self-controlled case series studies: half included concomitant users of warfarin + one of eight muscle relaxants; half included concomitant users of an inhaled corticosteroid (ICS) + one of eight muscle relaxants. The ICS analyses served as negative control comparisons. In each study, we calculated incidence rate ratios (IRRs) comparing thromboembolism rates in the co-exposed versus warfarin/ICS-only exposed person-time, adjusting for time-varying confounders. Results: Among ~70 million persons, we identified 8693 warfarin-treated subjects who concomitantly used a muscle relaxant, were hospitalized for thromboembolism, and met all other inclusion criteria. Time-varying confounder-adjusted IRRs ranged from 0.31 (95% confidence interval: 0.13–0.77) for metaxalone to 3.44 (95% confidence interval: 1.53–7.78) for tizanidine. The tizanidine finding was robust after quantitatively adjusting for negative control ICS findings, and in numerous prespecified secondary analyses. Conclusions: We identified a potential >3-fold increase in the rate of hospitalized thromboembolism in concomitant users of warfarin + tizanidine vs. warfarin alone. Alternative explanations for this finding include confounding by indication, a native effect of tizanidine, or chance.