Trust is valuable social capital that is essential for effective partnerships to improve a community’s health. Yet, how to establish trust in culturally diverse communities is elusive for many researchers, practitioners, and agencies. The purpose of this qualitative study was to obtain perspectives of individuals working for a nongovernmental organization (NGO) about gaining community trust in Malawi in order to mitigate the impact of HIV/AIDS. Twenty-six interviews were conducted over 12 months. Content analysis revealed the relationship between NGO staff and the community is crucial to gaining community trust. Gender, social context, and religious factors influence the establishment of trust within the relationship, but NGO assumptions about the community can erode community trust. Nurses and other health professionals working with the NGOs can help create conditions to build trust in an ethically and culturally sensitive manner whereby communities can develop processes to address their own health concerns.