Gastrointestinal symptoms (GIS) have been reported repeatedly in people with autism spectrum disorder (ASD) and studies have reported interesting correlations between severity of behavioral and gastrointestinal symptoms. Growing evidence indicates that the gut microbiota in ASD is altered with various shifts described at different taxonomic levels, pointing to the importance of considering the gut–brain axis in treatment of these disorders. Probiotics are live beneficial bacteria that are ingested as food or customized pills. These beneficial bacteria, when added in sufficient amounts, can correct the dysbiosis. Because probiotics have shown success in treating irritable bowel syndrome (IBS), it is plausible to investigate whether they can induce alleviation of behavioral symptoms as well. Probiotics show, in some clinical studies, their potential benefits (1) in improving gastrointestinal dysfunction, (2) in correcting dysbiosis, (3) in consequently reducing the severity of ASD symptoms. This review compiles data from selected studies that investigate these benefits and the mechanisms that mediate these effects, which include the production of metabolites, hormones, and neurotransmitters and the regulation of pro-inflammatory and regulatory cytokines. Future research based on more randomized, controlled studies with a larger population size and standardized use of strains, concentration of probiotics, duration of treatments, and methods of DNA extraction is still needed in this area, which may lead to more robust results.