Prebiotics have gained much attention in recent years as functional food ingredients. This has encouraged researchers to look for sustainable alternative sources of prebiotics. Prebiotics help in the modulation of the human intestinal microbiota and thereby improve host health. Chicory, asparagus, and Jerusalem artichoke are some conventional prebiotics that have been extensively studied. Mushrooms are rich sources of medicinal foods as well as bioactive polysaccharides and essential amino acids. They contain large amounts of chitin, mannans, galactans, xylans, glucans, krestin, lentinan, and hemicellulose, thus making it a potential candidate for prebiotics. They are also rich sources of fibers, proteins, and antioxidants. Several mushroom species like Ganoderma lucidum, Pleurotus ostreatus, Hericium erinaceus, Agaricus bisporus, and Lentinula edodes are rich in medicinal properties that have an array of applications. These medicinal mushrooms can be repurposed to regulate gut microbiota. In this review, we discuss the prebiotic effects of different mushroom species on probiotic organisms. We also reviewed the potential of mushroom waste as novel, cheap, and alternative sources of prebiotics.