Embankments filled with disintegrated carbonaceous mudstone (DCM) are prone to uneven settlements because of water-softening property and secondary disintegration of carbonaceous mudstone. To address this problem, nano-Al²O³ and cement were proposed in this study to improve the strength of DCM. Many nano-Al²O³- and cement-modified DCM (NACDCM) specimens with various nano-Al²O³ contents were prepared. Unconfined compression tests and triaxial compression tests were performed to examine the strengths of NACDCM under different conditions. Moreover, X-ray diffraction (XRD) analyses and scanning electron microscopy (SEM) observations were performed to reveal the microscopic mechanism for modification of the NACDCM. Macroscopic results showed that the unconfined compressive strength of NACDCM reached maximum when the nano-Al²O³ content was 0.2%. The cohesion showed positive correlation with nano-Al²O³ content while the angle of internal friction presented negative correlation with nano-Al²O³ content. Moreover, microscopic results indicated that nano-Al²O³ and cement improved the strength of NACDCM, mainly through cement hydration reaction, pozzolanic reaction, ion exchange, gel effect and filling effect.