The prevalence of female genital mutilation/cutting (FGM/C) in Nigeria is on the rise, although the practice has no known medical/health benefits. This study aims to assess FGM/C’s effect on breastfeeding outcomes and to identify the role of women’s attitudes and their access to healthcare services on these relationships. Associations between FGM/C and breastfeeding outcomes were measured using multi-logistic regression. About 32% of women underwent FGM/C, and 23% believed FGM/C should continue. Women exposed to FGM/C were less likely to initiate early breastfeeding (OR = 0.56, [95% CI = 0.47–0.66]) or to breastfeed exclusively (0.64, [0.57–0.73]). FGM/C acceptance reduced odds of early initiation of breastfeeding (0.57, [0.45–0.73]) (p for interaction < 0.001) and exclusive breastfeeding (0.65, [0.59–0.78]) (p for interaction < 0.001). Four or more antenatal care visits while pregnant modified the associations between FGM/C and early initiation (1.55, [1.26–1.90) (p for interaction < 0.001) or exclusive breastfeeding (2.01, [1.73–2.330]) (p for interaction < 0.001), respectively. FGM/C is associated with breastfeeding outcomes, but this association may be improved with healthcare access and attitudinal changes towards FGM/C. Targeted public health education interventions raising awareness about FGM/C and breastfeeding and policy changes increasing access to prenatal healthcare services in underserved areas are recommended.