Two stable austenitic steels, 20Cr-11Ni-5Mn-0.3N (wt%) stainless steel (STS) and 18Mn-1.5Al-0.6C (wt%) twinning-induced plasticity steel (TWIP), were investigated to understand the effect of grain size on hydrogen embrittlement (HE). Grain refinement promoted HE in the STS but suppressed HE in the TWIP. These opposite effects occurred because the steel composition affected deformation mechanism. Cr-N pair enhanced short-range ordering (SRO) in STS, which promoted planar slip and delayed mechanical twinning. In contrast, TWIP exhibited mechanical twinning which was more active in coarser grains. Final dislocation density after tensile deformation was increased by grain refinement in STS, but was decreased in TWIP. The damaging effects of hydrogen on strain energy at interfaces and on interfacial bonding strength were controlled by dislocation density; therefore, increase in dislocation density led to increase in susceptibility to HE.