The effect of Cr and Mo contents on the hydrogen embrittlement of tempered martensitic steels was investigated in this study. After the steels with different Cr and Mo contents were austenitized at 820 °C for 90 min, they were tempered at 630 °C for 120 min. The steels were composed of fully tempered martensite with a lath-type microstructure, but the characteristics of the carbides were dependent on the Cr and Mo contents. As the Cr and Mo contents increased, the volume fraction of film-like cementite and prior austenite grain size decreased. After hydrogen was introduced into tensile specimens by electrochemical charging, a slow strain-rate test (SSRT) was conducted to investigate hydrogen embrittlement behavior. The SSRT results revealed that the steel with lower Cr or lower Mo content showed relatively poor hydrogen embrittlement resistance. The hydrogen embrittlement resistance of the tempered martensitic steels increased with increasing Mo content, because the reduction in the film-like cementite and prior austenite grain size plays an important role in improving hydrogen embrittlement resistance. The results indicate that controlling the Cr and Mo contents is essential to achieving a tempered martensitic steel with a combination of high strength and excellent hydrogen embrittlement resistance.