When trusted, Community Health Workers (CHWs) can contribute to improving maternal and newborn health outcomes in low- and middle-income countries through education. Issues of acceptability of CHWs by communities were explored through experiences gained in a qualitative study that is part of a cluster randomized trial in East Uganda. Initially, focus group discussions with key community members and leaders were undertaken regarding preventative health and 40 CHWs were observed making home visits by supervisors during the initial 6 months of fieldwork of the trial in eight villages in the Jinja District in Uganda. The results were analyzed using the 5-SPICE framework. Observation of CHWs in the field identified a number of unanticipated issues including a general mistrust of the public health system by community members in areas that had an impact on maternal and newborn health. At the outset, CHWs often did not trust their own abilities and faced community expectations that they would provide curative rather than preventative care. Early community engagement, non-threatening home visits that enhanced friendship and supportive supervision improved the confidence of the CHWs and improved the trust and acceptance of the CHWs and the willingness of the community members to act on what was discussed.