A large amount of high water content mud is generated at civil engineering works and disaster sites, and the high water content mud is subjected to dehydration treatment and finally disposed in landfills. As for a method of recycling high water content mud, fiber-cement-stabilized soil method has been developed. Failure strength and failure strain of fiber-cement-stabilized soil have been investigated through unconfined compression test. However, there are few measured data of the shear strength parameters compared to failure strength and failure strain. In this study, to evaluate shear strength parameters of fiber-cement-stabilized soil, box shear test and unconfined compression test are conducted with different additive amount of cement and paper debris to clarify the effect of additive conditions on the shear strength parameters of modified soil. Furthermore, the improvement was performed on mud with different particle size distribution, and the effect of the difference in soil properties on the shear strength parameters was clarified. The results showed that the internal friction angle increased as increasing the amount of paper debris. In addition, when the additive amount of cement increased, the cohesion increased. In the case of unconfined compression test, it was confirmed that the failure strength and failure strain tended to increase due to the increase of the additive amount of cement and paper debris. Furthermore, it is suggested that the shear strength parameters of fiber-cement-stabilized soil has close relationship with the grain size characteristics of mud.