Sexually transmitted diseases (STDs), HIV, and AIDS disproportionately affect the African American community. In 1999, the rates of gonorrhea and primary and secondary syphilis among African Americans in the United States were approximately 30 times greater than those rates in Whites. Although African Americans represent only 12% of the population nationwide, they constitute 37% of the cumulative AIDS cases. In North Carolina’s Durham County, African Americans accounted for 88% (553) of the HIV cases reported as of December 2000. There remains a demand for prevention efforts that are culturally relevant, incorporating the social norms and values of the African American community. Through the Barber and Beautician STD/HIV Peer Educator Program of the Durham County Health Department’s Project StraighTalk (PS), local barbers and beauticians provide condoms, educational materials, and education to their clients about STDs/HIV. In collaboration with PS, Lewis and Shain performed a needs assessment of the program, including interviews with stylists and clients, to inform program enhancement and materials development. This article describes the needs assessment process, with a specific focus on the challenges of working closely with a community and the lessons learned.