In order to improve the deficient engineering properties of muddy soil, the use of flue gas desulfurization gypsum (FDG) and guar gum (GG) as composite cementitious materials, supplemented with basalt fiber (BF) for reinforcement, is proposed. The appropriate mixing ratio range for each material was determined through individual mixing experiments. Then the central composite design and response surface method were used to optimize the proportions of the three components. The mechanical properties and microscopic mechanisms of the modified samples were evaluated by unconfined compressive strength (UCS) tests, water stability tests, permeability tests, consolidation tests, disintegration tests, and microscopic characterization techniques (XRD, SEM, MIP, and FTIR). The results show that the optimal contents of GG, FDG, and BF are 1.35%, 3.00%, and 0.32% of the dry soil mass, respectively. The modified material is collectively referred to as GDF. At 14 days of curing, the shear strength reaches 180.92 kPa. The UCS increases from 177.98 kPa at 3 days to 576.32 kPa at 14 days. After 14 days of water immersion, the disintegration amount is 8.05%. The saturated permeability coefficient decreases from 1.09×10-5 cm/s in the untreated sample to 2.32×10-6 cm/s after 14 days of curing. The cumulative pore volume decreases from 0.25 mL/g to 0.18 mL/g. XRD and SEM analysis shows that acicular ettringite crystals are formed by the reaction of FDG with minerals rich in the aluminum phase. FTIR analysis shows that hydrogen bonds can be formed by GG to bond particles. A cemented and fiber-reinforced composite structure is formed by hydrogen bonds, cementitious crystals, and BF. The pore system is refined and the interfacial adhesion between soil particles and fibers is improved by this structure. The GDF-modified muddy soil shows improved strength, water stability, and impermeability. It provides a feasible technical approach for the resource utilization and engineering disposal of muddy soil.