Hydrogen gas (H2) has been shown as an important factor in plant tolerance to abiotic stresses, but the underlying mechanisms remain unclear. In the present study, the effects of H2 and its interaction with nitric oxide (NO) on alleviating cadmium (Cd) stress in Brassica campestris seedlings were investigated. NO donor (SNP) or hydrogen-rich water (HRW) treatment showed a significant improvement in growth of Cd-stressed seedlings. Cd treatment upregulated both endogenous NO and H2 (36% and 66%, respectively), and the increase of H2 was prior to NO increase. When treated with NO scavenger (PTIO) or NO biosynthesis enzyme inhibitors (L-NAME and Gln), HRW-induced alleviation under Cd stress was prevented. Under Cd stress, HRW pretreatment significantly enhanced the NO accumulation, and together up-regulated the activity of NR (nitrate reductase) and expression of NR. HRW induced lower reactive oxygen species (ROS), higher AsA content, enhanced activity of POD (peroxidase) and SOD (superoxide dismutase) in seedling roots were inhibited by PTIO, L-NAME and Gln. Through proteomic analysis, the level of 29 proteins were changed in response to H2 and NO-induced amelioration of Cd stress. Nearly half of them were involved in oxidation-reduction processes (about 20%) or antioxidant enzymes (approximately 20%). These results strongly indicate that in Cd-stressed seedlings, pretreatment with HRW induces the accumulation of H2 (biosynthesized or permeated), which further stimulates the biosynthesis of NO through the NR pathway. Finally, H2 and NO together enhance the antioxidant capabilities of seedlings in response to Cd toxicity.