Cadmium (Cd) pollution is a growing concern worldwide, because it threatens human health through the food chain. Woody plants, such as the pioneer species black locust (Robinia pseudoacacia L.), are widely used in phytoremediation of Cd-contaminated soils, but strongly differ in Cd tolerance. Nitric oxide (NO), a highly reactive gas of biogenic and anthropogenic origin, has been shown to protect plants to Cd exposure. We investigated the protective mechanism of NO against Cd toxicity in black locust using physiological, transcriptomic and metabolomic approaches. We studied the correlation between cell wall traits, genes, and metabolites. The findings indicated that NO improved the growth of black locust under Cd exposure and elevated the fraction of Cd in the cell wall. NO increased cell wall thickness by stimulating the biosynthesis of pectin, cellulose, hemicellulose, and lignin. Transcriptomic and metabolomic analyses demonstrated that NO upregulated genes related to root cell wall biosynthesis and increased the accumulation of related metabolites, thereby increasing the Cd resistance of black locust. Our results elucidated a molecular mechanism underlying NO-mediated Cd tolerance in black locust and provided novel insights for phytoremediation of Cd-polluted soils by woody plants.