Background: Obesity is associated with early cessation of breastfeeding. Breastfeeding is multi-factorial, and several factors contribute to this association. Our aim was to investigate to what extent socio-demographic and psychosocial characteristics, parity and prenatal conditions could explain the association between high BMI and early cessation of breastfeeding. Methods: We used data from a randomized trial of 1597 Danish mothers of singleton infants. Self-reported maternal postnatal weight and height were available from 1375 (86%). High BMI was defined as body mass index ≥32 kg/m2 at ∼17 days after delivery. Outcome was cessation of exclusive breastfeeding by 17 weeks post-partum used in proportional hazards regression models. Results: In the unadjusted analysis, mothers with high post-partum BMI compared with other mothers had a significantly higher rate of cessation of exclusive breastfeeding, and were more frequently characterized by socio-demographic, psychosocial, perinatal and behavioural factors known to increase the risk of early breastfeeding cessation. In the adjusted analyses (n = 1226), the association between BMI and duration of exclusive breastfeeding depended on parity (P = 0.03). Among primiparae, high BMI was associated with nearly double the risk of early cessation of exclusive breastfeeding (HR = 1.74, 95% CI 1.21–2.50). Among multiparae, the association disappeared when adjusted for socio-demographic factors and previous breastfeeding experience (HR = 0.89, 95% CI 0.62–1.28). Conclusion: Parity and previous breastfeeding experience are important factors to include when studying the association between BMI and breastfeeding duration. Intervention to extend the duration of lactation among obese mothers should focus on those with no or little previous breastfeeding experience.