Background: Despite lower cancer screening rates and survival rates in the Medicaid population compared with those with private insurance, there is a dearth of population-based, evidence-based interventions targeting Medicaid clients to address this problem. Methods: This study reports results of a population-based randomized controlled trial (RCT) among all individuals enrolled in Minnesota's Medicaid program who were overdue for breast cancer (n = 22,113) and/or colo-rectal cancer (n = 94,294) screening. Individuals were randomized to intervention or control groups. The intervention group received persuasive and innovative direct mail materials coupled with a $20 incentive for using their Medicaid benefit to get screened. Direct mail materials provided a phone number to a call center staffed by patient navigators who addressed barriers and scheduled appointments via three-way calls. The control group received the intervention 15 months later. Primary outcomes were completion of mammography or colonoscopy within 12 weeks of the intervention. Billing claims served as evidence of screening. Results: Multivariate logistic regression showed significant differences for both breast cancer (P < 0.001) and colorectal cancer (P < 0.01). The odds of receiving a mammogram for the treatment group were significantly higher than the control group [OR= 1.30; 95% confidence interval (95% CI) = 1.16-1.46], and the treatment group was more likely to receive a colonoscopy than the control group (OR = 1.12; 95% CI = 1.04-1.21). Conclusions: This population-based intervention increased breast cancer and colorectal cancer screening in a Medicaid population overdue for screening. Impact: These findings may have broad application for reaching individuals who generally remain outside the health care system despite having public health insurance.