Background. There is limited research investigating the composition of the gastrointestinal microbiota in individuals with celiac disease (CoeD) reporting only partial symptom improvement despite adherence to a strict gluten-free diet (GFD). The aim of this research was to determine if the gastrointestinal microbiota could be altered by probiotic bacteria and provide a potential new therapy for this subgroup. Methods. A multicentre RCT was conducted between January and August 2011 in Australia. Participants included 45 people with CoeD reporting only partial symptom improvement despite adherence to a strict GFD for a minimum of 12 months. Participants took 5 g of VSL#™ probiotic formulation (n = 23) or 5 g placebo (n = 22) orally twice daily for 12 weeks. The main outcome measured was the efficacy of the probiotic formula in altering faecal microbiota counts between baseline and week 12. Safety was determined by safety blood and monitoring adverse events. Results. SPSS™ multivariate repeated measures analysis (95th confidence level) revealed no statistically significant changes between the groups in the faecal microbiota counts or blood safety measures over the course of the study. Conclusion. The probiotic formula when taken orally over the 12-week period did not significantly alter the microbiota measured in this population. The trial was registered with Australian and New Zealand Clinical Trials Register ACTRN12610000630011.