Lacto-fermented sauerkraut contains a natural variety of lactic acid bacteria (LAB) and has not previously been studied in the treatment of irritable bowel syndrome (IBS) patients. The present study investigated the effect of a daily lacto-fermented sauerkraut supplement in relation to IBS patients' gastrointestinal symptoms and gut microbiota composition. A randomized double-blinded intervention was conducted with 34 Norwegian IBS patients. The patients were consuming either pasteurized sauerkraut (PS; n = 15) or unpasteurized sauerkraut (UPS; n = 19) as a supplement to their daily diet for 6 weeks. The differences in change of symptoms were assessed using the questionnaire IBS-Symptom Severity Score (IBS-SSS) measured at the baseline, and at weeks 2, 4, 6 and 8 (follow-up). The gut microbiota composition was analysed using 16S rRNA gene amplicon sequencing of faecal samples from the baseline and week 6. The mean change in IBS-SSS was -38.57 ± 17.08 PS vs. -56.99 ± 16.92 UPS and was significantly improved in both groups (P < 0.04), while the improvement in symptoms was not different between the intervention groups. The sauerkraut intervention (pasteurized or not) also led to significant gut microbiota compositional changes as determined by 16S rRNA gene amplicon sequencing (un-weighted UniFrac: P = 0.001, weighted UniFrac: P = 0.001). Sauerkraut related LAB in feces (Lactobacillus plantarum and Lactobacillus brevis) were significantly more often present in the UPS-group. In conclusion lacto-fermented sauerkraut had an effect on IBS patients' symptoms and gut microbiota even though the study was underpowered. Our results indicate that the observed effect to a larger extent can be attributed to the potential prebiotics in lacto-fermented sauerkraut rather than the viable LAB. Future studies with greater statistical power are needed to clarify the possible effects of LAB from lacto-fermented sauerkraut in the treatment of IBS patients.