BACKGROUND: Australia has a comparatively high incidence of colorectal (bowel) cancer; however, population screening uptake using faecal occult blood test (FOBT) remains low. This study will determine the impact on screening participation of a novel, Internet-based Personalised Decision Support (PDS) package. The PDS is designed to measure attitudes and cognitive concerns and provide people with individually tailored information, in real time, that will assist them with making a decision to screen. The hypothesis is that exposure to (tailored) PDS will result in greater participation in screening than participation following exposure to non-tailored PDS or resulting from the current non-tailored, paper-based approach. METHODS/DESIGN: A randomised parallel trial comprising three arms will be conducted. Men and women aged 50-74 years (N = 3240) will be recruited. They must have access to the Internet; have not had an FOBT within the previous 12 months, or sigmoidoscopy or colonoscopy within the previous 5 years; have had no clinical diagnosis of bowel cancer. Groups 1 and 2 (PDS arms) will access a website and complete a baseline survey measuring decision-to-screen stage, attitudes and cognitive concerns and will receive immediate feedback; Group 1 will receive information 'tailored' to their responses in the baseline survey and group 2 will received 'non-tailored' bowel cancer information. Respondents in both groups will subsequently receive an FOBT kit. Group 3 (usual practice arm) will complete a paper-based version of the baseline survey and respondents will subsequently receive 'non-tailored' paper-based bowel cancer information with accompanying FOBT kit. Following despatch of FOBTs, all respondents will be requested to complete an endpoint survey. Main outcome measures are (1) completion of FOBT and (2) change in decision-to-screen stage. Secondary outcomes include satisfaction with decision and change in attitudinal scores from baseline to endpoint. Analyses will be performed using Chi-square tests, analysis of variance and log binomial generalized linear models as appropriate. DISCUSSION: It is necessary to restrict participants to Internet users to provide an appropriately controlled evaluation of PDS. Once efficacy of the approach has been established, it will be important to evaluate effectiveness in the wider at-risk population, and to identify barriers to its implementation in those settings. TRIAL REGISTRATION: Australian New Zealand Clinical Trials Registry ACTRN12610000095066.