Chronic fatigue syndrome (CFS) is complex illness of unknown etiology. Among the broad range of symptoms, many patients report disturbances in the emotional realm, the most frequent of which is anxiety. Research shows that patients with CFS and other so-called functional somatic disorders have alterations in the intestinal microbial flora. Emerging studies have suggested that pathogenic and non-pathogenic gut bacteria might influence mood-related symptoms and even behavior in animals and humans. In this pilot study, 39 CFS patients were randomized to receive either 24 billion colony forming units of Lactobacillus casei strain Shirota (LcS) or a placebo daily for two months. Patients provided stool samples and completed the Beck Depression and Beck Anxiety Inventories before and after the intervention. We found a significant rise in both Lactobacillus and Bifidobacteria in those taking the LcS, and there was also a significant decrease in anxiety symptoms among those taking the probiotic vs controls (p = 0.01). These results lend further support to the presence of a gut-brain interface, one that may be mediated by microbes that reside or pass through the intestinal tract.