The societal burden of opioid use disorder (OUD) is considerable and contributes to increased healthcare costs and overdose deaths. However, the burden is not well understood. The purpose of this analysis is to estimate the state Medicaid programs' costs for treating OUD and how these costs have changed over time. We used data from the Medicaid Analytic eXtract files from 17 states between 1999 and 2013 to examine the healthcare costs associated with OUD. Inpatient, outpatient, and prescription medication costs related to the treatment of OUD were included, as were excess costs for other healthcare services (eg, general medical care) for individuals with OUD relative to a comparison group of individuals without OUD matched on age, sex, and state. We then extrapolated our results to the entire US Medicaid population using population-based sample weights. All costs were adjusted for inflation and are reported in 2017 US dollars. During our study period, the number of patients who were diagnosed with OUD increased 378%, from 39,109 (0.21% of total Medicaid enrollment) in 1999 to 186,979 (0.60% of total Medicaid enrollment) in 2013 in our 17-state sample. Even after adjusting for inflation, total Medicaid costs associated with OUD more than tripled during this time, reaching more than $3 billion in 2013, from $919 million in 1999. Most of this growth was due to excess non-OUD treatment costs for patients with OUD, which increased 363% over the period; the rate of growth is triple the expenditures for OUD treatment services. When the results were extrapolated to the entire United States, the Medicaid costs associated with OUD increased from more than $2 billion in 1999 to more than $8 billion in 2013. The total cumulative costs that were associated with OUD for this extrapolated 50-state sample over a 15-year time period amounts to more than $72.4 billion. OUD imposes considerable financial burden on state Medicaid programs, and the burden is increasing over time.