To compare receipt of contraception and method effectiveness in the early postpartum period among women with and without a recent preterm birth (PTB). We used data from North Carolina birth certificates linked to Medicaid claims. We assessed contraceptive claims with dates of service within 90 days of delivery among a retrospective cohort of women who had a live birth covered by Medicaid between September 2011 and 2012 (n = 58,201). To estimate the odds of receipt of contraception by PTB status (24-36 weeks compared to 37-42 weeks [referent]), we used logistic regression and tested for interaction by parity. To estimate the relationship between PTB and method effectiveness based on the Center for Disease Control and Prevention Levels of Effectiveness of Family Planning Methods (most, moderate and least effective [referent]), we used multinomial logistic regression. Less than half of all women with a live birth covered by Medicaid in North Carolina had a contraceptive claim within 90 days postpartum. Women with a recent PTB had a lower prevalence of contraceptive receipt compared to women with a term birth (45.7% vs. 49.6%). Women who experienced a PTB had a lower odds of receiving contraception. When we stratified by parity, women with a PTB had a lower odds of contraceptive receipt among women with more than two births (0.79, 95% CI 0.74-0.85), but not among women with two births or fewer. One-fourth of women received a most effective method. Women with a preterm birth had a lower odds of receiving a most effective method (0.83, 95% CI 0.77-0.88) compared to women with a term birth. Contraceptive receipt was low among women with a live birth covered by Medicaid in North Carolina. To optimize contraceptive use among women at risk for subsequent preterm birth, family planning strategies that are responsive to women's priorities and context, including a history of preterm birth, are needed. Access to free or affordable highly effective contraception is associated with reductions in preterm birth. Self-report data indicate that women with a very preterm birth (PTB) are less likely to use highly or moderately effective contraception postpartum compared to women delivering at later gestational ages. Using Medicaid claims data, we found that less than half of all women with a Medicaid covered delivery in North Carolina in 2011-2012 had a contraceptive claim within 90 days postpartum, and one fourth received a most effective method. Women with a PTB and more than two children were least likely to receive any method. Family planning strategies that are responsive to women's priorities and context, including a history of preterm birth, are needed so that women may access their contraceptive method of choice in the postpartum period.