We recruited women (primarily non-Hispanic White) from 14 rural, segregated counties in a Northeastern US state for an explanatory sequential study: 100 women (ages 50–65 years) completed a survey, and 16 women participated in focus groups. We sought to identify personal (e.g., healthcare mistrust) and environmental (e.g., travel time to healthcare providers) factors related to colorectal and cervical cancer screening. Quantitatively, 89% of participants were up-to-date for cervical screening, and 65% for colorectal screening. Factors interacted such that compounding barriers were associated with lower odds of screening (e.g., insurance status and healthcare mistrust: interaction p = .02 for cervical; interaction p = .05 for colorectal). Qualitatively, three themes emerged regarding barriers to screening: privacy concerns, logistical barriers, and lack of trust in adequacy of healthcare services. While cancer screening was common in rural, segregated counties, women who reported both environmental and personal barriers to screening had lower uptake. Future interventions to promote screening can target these barriers. Supplementary Information The online version contains supplementary material available at 10.1007/s13187-021-02069-0.