Obesity is a major global health problem which is associated with various diseases and psychological conditions. Increasing understanding of the relationship between obesity and gut microbiota has led to a worldwide effort to use microbiota as a treatment for obesity. However, several clinical trials have shown that obesity treatment with single strains of probiotics did not achieve as significant results as in animal studies. To overcome this limitation, we attempted to find a new combination that goes beyond the effects of probiotics alone by combining probiotics and a natural substance that has a stronger anti-obesity effect. In this study, we used a diet-induced obesity mouse (DIO) model to investigate the effects of combining Lactobacillus plantarum HAC03 with Garcinia cambogia extract, as compared to the effects of each substance alone. Combining L. plantarum HAC03 and G. cambogia, treatment showed a more than two-fold reduction in weight gain compared to each substance administered alone. Even though the total amount administered was kept the same as for other single experiments, the combination treatment significantly reduced biochemical markers of obesity and adipocyte size, in comparison to the treatment with either substance alone. The treatment with a combination of two substances also significantly decreased the gene expression of fatty acid synthesis (FAS, ACC, PPARγ and SREBP1c) in mesenteric adipose tissue (MAT). Furthermore, 16S rRNA gene sequencing of the fecal microbiota suggested that the combination of L. plantarum HAC03 and G. cambogia extract treatment changed the diversity of gut microbiota and altered specific bacterial taxa at the genus level (the Eubacterium coprostanoligenes group and Lachnospiraceae UCG group) and specific functions (NAD salvage pathway I and starch degradation V). Our results support that the idea that the combination of L. plantarum HAC03 and G. cambogia extract has a synergistic anti-obesity effect by restoring the composition of the gut microbiota. This combination also increases the abundance of bacteria responsible for energy metabolism, as well as the production of SCFAs and BCAAs. Furthermore, no significant adverse effects were observed during the experiment.