Objectives. To test the effectiveness of a preclinical, telephone-based patient navigation intervention to encourage colorectal cancer (CRC) screening among older Black men. Methods. We conducted a 3-parallel-arm, randomized trial among 731 self-identified Black men recruited at barbershops between 2010 and 2013 in New York City. Participants had to be aged 50 years or older, not be up-to-date on CRC screening, have uncontrolled high blood pressure, and have a working telephone. We randomized participants to 1 of 3 groups: (1) patient navigation by a community health worker for CRC screening (PN), (2) motivational interviewing for blood pressure control by a trained counselor (MINT), or (3) both interventions (PLUS). We assessed CRC screening completion at 6-month follow-up. Results. Intent-to-treat analysis revealed that participants in the navigation interventions were significantly more likely than those in the MINT-only group to be screened for CRC during the 6-month study period (17.5% of participants in PN, 17.8% in PLUS, 8.4% in MINT; P <.01). Conclusions. Telephone-based preclinical patient navigation has the potential to be effective for older Black men. Our results indicate the importance of community-based health interventions for improving health among minority men.