Rationale Male participation in screening for bowel cancer is sub-optimal. Theory-based interventions provide a means of improving screening uptake. Objective To test the efficacy of modifying consumer invitation material in line with continuum and stage theories of health behaviour on screening participation. Methods N = 9216 Australian men aged 50–74 years were randomised to one of four trial arms in a 2 × 2 factorial design randomised controlled trial. Participants received either standard invitation material (control group), or combinations of modified advance-notification and invitation letters. A subsample completed baseline and endpoint behavioural surveys. Results Participants who received the modified advance notification letter were 12% more likely to screen than those who received the standard version (RR = 1.12, χ2(1) = 10.38, p = 0.001). The modified invitation letter did not impact screening uptake (RR = 0.97, χ2(1) = 0.63, p = 0.424). No significant changes in psychological variables due to the intervention were observed. Conclusion Modifications to advance notification letters in line with health behaviour theories significantly improves screening uptake in men. Trial registration Australian New Zealand Clinical Trials Registry: ACTRN12612001122842 https://www.anzctr.org.au/Trial/Registration/TrialReview.aspx?id=362688.