This study aimed to improve the mechanical properties of predisintegrated carbonaceous mudstone (PCM) used as an embankment fill. The four factors used in the orthogonal design test were nano-Al2O3 content, cement content, water content and compaction. After the tests were completed the strength characteristics and micromechanisms of PCM modified by nano-Al2O3 and cement were studied using triaxial compression tests, X-ray diffraction analysis and SEM observations. The results show that the failure mode of PCM changes from bulging failure to shear failure when the nano-Al2O3 and cement contents are increased. The order in which the factors affected the cohesion of PCM is cement content, nano-Al2O3 content, water content and compaction. At a given cement content, the cohesion of PCM with an optimal compaction of 96% and a water content of 8% increases and then decreases with increasing nano-Al2O3 content. The increase in the internal friction angle is proportional to the nano-Al2O3 content when the cement content is between 0 and 4%. Controlling the nano-Al2O3 and cement contents to 0.3 and 8%, respectively, results in a synergistic effect of both materials on the shear strength. Nano-Al2O3 improves the cohesion and friction strength of PCM by accelerating the hydration of cement and optimizing the structure of the hydration products.