This study investigated self-efficacy in breastfeeding support among public health nurses (PHNs) working at maternal and child health (MCH) services in Japanese municipalities, and its related factors such as education, working experience, breastfeeding experience, and postgraduate/continuous education. Directors of the MCH divisions were requested to select one PHN to answer the self-report questionnaires sent. The questionnaires were collected from October 2010 to January 2011. Of the 1750 questionnaires sent, 831 were returned (response rate: 47.5%); 102 were excluded from analysis because of missing data (valid response rate: 41.7%). After adjusting the weights of PHN sampling and collection rates by prefecture and population size, Model 1 of the multiple regression analysis showed that the self-efficacy in breastfeeding support was significantly higher in large/urban municipalities (β = 0.13) and in the Kanto district. Model 2 revealed that self-efficacy was significantly associated with working experience (β = 0.13) and breastfeeding experience (β = 0.22) but not with educational background. Model 3 showed that self-efficacy was significantly associated with postgraduate education (β = 0.14) and continuous education (β = 0.12). This suggested that PHNs’ self-efficacy increased through self-enrichment. It is necessary to create training opportunities about breastfeeding support for PHNs—especially those working in remote and/or small municipalities— and to provide them with new and important information.