There are between 1000 and 1150 bacterial species that can be found in the human microbiome along with different species of viruses, fungi, protozoa and archaea. While inhabiting the distal small bowel, caecum and colon, their task is to metabolize substances in the lumen to provide an additional source of nutrients. Products that contain these commensal, nonpathogenic, microorganisms and that benefit the host are called probiotics. The most commonly used microorganism strains are the bacterial genera Lactobacillus and Bifidobacterium, as well as the probiotic yeast Saccharomyces boulardii. There is vast body of evidence documenting their beneficial effect to the host by modulating the host’s immune system or by affecting other undesired microorganisms or their products. However, like every other microorganism, bacteria and yeast require certain substances which would provide them with a suitable environment to grow. These substances are non-viable food components that confer health benefits to the host, and are also known as prebiotics. Prebiotic compounds are defined as carbohydrates or soluble dietary fibers such as inulin, β-glucans and fructooligosaccharides. Different prebiotics stimulate the growth of different bacterial species and it is important for them to reach the colon unchanged in order to stimulate the growth and activity of intestinal microbiota. Many studies have shown a significant increase in number of probiotic bacteria in the presence of mushroom polysaccharides. Even edible mushrooms such as M. procera and S. crispa demonstrated high stimulation on the growth of lactobacilli and thus confirmed their potential use as nutraceuticals.