Colorectal cancer (CRC) is one of the leading causes of cancer-related deaths in the United States. Randomized controlled trials have shown that annual screening fecal occult blood testing (FOBT) reduces CRC mortality and incidence. However, patient compliance with FOBT is low. To determine whether a mailed educational reminder increases FOBT card return rates and to examine predictors of FOBT compliance. Blinded, randomized, controlled trial at the Veteran Affairs Medical Center, San Diego, California. Seven hundred and seventy-five consecutive patients ≥50 years of age referred by their primary care physicians for FOBT. Patients were randomly assigned to the usual care group or the intervention group. Ten days after picking up the FOBT cards, a 1-page reminder with information related to CRC screening was mailed to the intervention group only. The primary outcome was proportion of returned FOBT cards after 6 months. Patient demographic, clinical characteristics and prior FOBT completed were collected for multivariate regression analysis. At 6 months after card distribution, 64.6% of patients in the intervention group returned cards compared with 48.4% in the control group (P < 0.001). Patients who received a mailed reminder (OR 2.02; 95% CI: 1.48–2.74) or have a prior history of returning the FOBT cards (OR 1.87; 95% CI: 1.29–2.70) were more likely to return the FOBT cards. Patients with current or recent illicit drug use were less likely to return the FOBT cards (OR 0.26; 95% CI: 0.13–0.50). A simple mailed educational reminder significantly increases compliance with FOBT for CRC screening.