Background Recruitment for research and clinical trials continues to be challenging. Prostate cancer is the most commonly diagnosed cancer in men and disproportionately affects African American men; thus, effective recruitment strategies are essential for this population. Objectives To focus on innovative and effective recruitment strategies for research on prostate cancer with minorities. Methods A systematic description is provided of the recruitment efforts for a hermeneutic phenomenological qualitative study of African American men's experiences in decision-making on whether or not to have a prostate cancer screening. Results Seventeen African American men were enrolled from rural Central Virginia. Recruiting strategies were targeted on places where African American men usually are found, but that are rarely used for recruitment: barbershops, community health centers, and churches. Word-of-mouth was used also, and the majority of the participants (n = 11) were reached through this method. Discussion Recruitment efforts have been noted to be particularly challenging among minorities, for numerous reasons. Making minority recruitment a priority in any research or clinical trial is essential in gaining a representative sample. Word-of-mouth is a powerful tool that is often forgotten, but should be looked at in further detail.