Colorectal cancer (CRC) is one of the leading causes of cancer-related deaths in Australia and a common cause of morbidity and mortality worldwide. Screening is an attractive option since there is an identifiable precursor lesion and the bowel is readily accessible for screening. In addition, the early detecting of CRC or adenoma has been proven to reduce CRC-associated mortality. The faecal-occult blood test (FOBT) is a widely-used cost-effective screening tool for large-scale bowel cancer screening programs. In 2006 a National Bowel Cancer Screening Program (NBCSP) was established in Australia, using an immunochemistry-based FOBT. The Program currently targets all Australians who turn 50, 55 or 65 years of age between January 2011 and December 2014. Despite the proven impact of screening on reducing bowel cancer mortality, the uptake of the NBCSP has been low. OBJECTIVES: To evaluate the cost-effectiveness of a patient-direct mailed advance notification letter, on participants of the NBCSP in Australia. METHODS: This study followed a hypothetical cohort of 50-year-old, 55-year-old and 65-year-old patients undergoing FOBT screening through a Decision analytic Markov model. The intervention compared two strategies: 1) Advance letter, NBCSP and FOBT compared with 2) NBCSP and FOBT. The main outcome measures were life years gained (LYG), quality-adjusted life years (QALY) gained and incremental cost-effectiveness ratio (ICER). RESULTS: An advance notification screening letter would yield an additional 54 per 100,000 CRC deaths avoided compared with no letter. The estimated cost-effectiveness was $3976 per LYG and $6976 per QALY gained. CONCLUSIONS: An advance notification letter in the NBCSP may have a significant impact on life years gained and cancer deaths avoided. It is cost-effective and offers a feasible strategy that could be rolled out across other screening program at an acceptable cost.