Objective To address problems such as the poor structure and fertility degradation in strongly acidic soils, we isolated acid-tolerant exopolysaccharide (EPS)-producing microorganisms, constructed a composite microbial inoculant, and evaluated its improvement effects on the structure and comprehensive fertility of acidic soils. Methods Target strains were obtained through primary and secondary screening from strongly acidic soils (pH<4.5) in Nanchuan, Chongqing and Qujing, Yunnan. After their antagonistic activity and plant growth-promoting traits were assessed, a composite microbial inoculant was constructed. A laboratory soil culture experiment was conducted to investigate changes in nutrient contents and aggregate composition in strongly acidic soils treated with different inoculants, comprehensively evaluate the fertility-improving effects of the inoculants, and clarify the correlation between aggregate formation and EPS content. Results Three strains—Paraburkholderia fungorum C3, Burkholderia cepacia A13, and Cystobasidium minutum B14—with acid tolerance and high EPS-producing capabilities were successfully isolated and screened out. All the strains exhibited the capabilities of secreting indole-3-acetic acid (IAA), synthesizing siderophores, and solubilizing phosphorus. When these strains were applied individually or as a composite inoculant to soils, the composite inoculant showed the best effect of improving soil nutrients, increasing the content of soil organic matter, alkaline-hydrolyzable nitrogen, available phosphorus, and available potassium by 4.51%, 13.92%, 4.92%, and 3.71%, respectively. Application of all the inoculants effectively promoted the formation of soil macro-aggregates, among which the single-strain inoculant C3 had the most significant effect in promoting aggregate formation, increasing the soil mean weight diameter (MWD) by 19.39%. The integrated fertility index of the soil treated with the composite inoculant reached 0.61, indicating the optimal comprehensive improvement effect. The single-strain inoculant C3 and the composite inoculant significantly increased the soil EPS content by 53.17% and 35.79%, respectively. Correlation analysis results showed that soil EPS had significantly positive correlations with macro-aggregate content and MWD, significantly promoting the formation and enhancing the stability of soil macro-aggregates. Conclusion The composite inoculant composed of the three acid-tolerant EPS-producing strains screened in this study effectively improved the soil structure and enhanced the integrated soil fertility. These findings lay a theoretical foundation for the development of biological agents for acidic soil remediation.