The mechanical behavior of cemented gangue backfill materials (CGBMs) is closely related to particle size distribution (PSD) of aggregates and properties of cementitious materials. Consequently, the true triaxial compression tests, CT scanning, SEM, and EDS tests were conducted on cemented gangue backfill samples (CGBSs) with various carbon nanotube concentrations (P _CNT) that satisfied fractal theory for the PSD of aggregates. The mechanical properties, energy dissipations, and failure mechanisms of the CGBSs under true triaxial compression were systematically analyzed. The results indicate that appropriate carbon nanotubes (CNTs) effectively enhance the mechanical properties and energy dissipations of CGBSs through micropore filling and microcrack bridging, and the optimal effect appears at P _CNT of 0.08wt%. Taking PSD fractal dimension (D) of 2.500 as an example, compared to that of CGBS without CNT, the peak strength (σ _p), axial peak strain (ε _1,p), elastic strain energy (U _e), and dissipated energy (U _d) increased by 12.76%, 29.60%, 19.05%, and 90.39%, respectively. However, excessive CNTs can reduce the mechanical properties of CGBSs due to CNT agglomeration, manifesting a decrease in σ _p, ε _1,p, and the volumetric strain increment (Δε _v) when P _CNT increases from 0.08wt% to 0.12wt%. Moreover, the addition of CNTs improved the integrity of CGBS after macroscopic failure, and crack extension in CGBSs appeared in two modes: detour and pass through the aggregates. The σ _p and U _d firstly increase and then decrease with increasing D, and porosity shows the opposite trend. The ε _1,p and Δε _v are negatively correlated with D, and CGBS with D = 2.150 has the maximum deformation parameters (ε _1,p = 0.05079, Δε _v = 0.01990) due to the frictional slip effect caused by coarse aggregates. With increasing D, the failure modes of CGBSs are sequentially manifested as oblique shear failure, “Y-shaped” shear failure, and conjugate shear failure.