The embankment of heavy-haul railway is typically subjected to greater dynamic loads than those of conventional and high-speed railways and thus exhibits greater deformations. The majority of heavy-haul railway embankment layers is comprised of coarse-grained soils (CGS). The primary objective of this paper is to investigate the strength and deformation characteristics of such coarse-grained soils under repeated train loading. For this purpose, a series of large-scale laboratory triaxial tests is conducted for the effects of varying dynamic stress amplitudes, confining pressures and moisture contents on the accumulated permanent deformation behavior. The characteristics of dynamic strength behavior with different combinations of static strength and confining pressure levels are analyzed. According to the permanent deformation accumulation characteristics, that is the increase of confining pressure or reduction of dynamic stress is helpful to enhance the soil stability of CGS obtained at different levels of deviatoric and confining stress values, a criterion for determining stable state of CGS is proposed, and the parameters of the criterion are given. The research results contribute to improving evaluation of the dynamic stability of heavy-haul railway embankment and to the establishment of the design philosophy based on the dynamic deformation control.