Martensite is an attractive crystalline structure to fabricate ultrafine grain steels by cold rolling and annealing because of its low equivalent strain. However, the deformation resistance of martensite increases inevitably with the increase in the carbon content of the steel. Accordingly, cracks are easily initiated in martensite before it reaches the desired strain, restricting the application of cold rolling and annealing to ultra-low and low-carbon steels. Thus, to extend the application of these methods from low to medium-carbon steel, compositional gradient steel was prepared by decarburizing medium-carbon steel. The carbon content increased from the surface layer to core layer in the gradient steel. The decarburized medium-carbon martensite was successfully cold rolled under large deformation with an equivalent strain of 1.5 with no microcracks on the sample surface. The microstructure and mechanical properties of the quenched and cold rolled gradient component steel were characterized and studied via OM, SEM, and tensile test. The experimental results revealed the gradient size of martensite along with the gradient carbon content in the microstructure. Further, different diffusion rates of carbon atoms during decarburization and austenitization resulted in the gradient austenite grain, which restrained the size of martensite. Compared with homogenous martensite of the experimental medium-carbon steel, the steel with gradient distribution of carbon exhibited low tensile strength, which decreased from 1700 MPa to 1525 MPa, but high tensile uniform elongation, which is increased by 40%; moreover, the gradient steel showed higher product of strength and elongation than homogeneous martensite steel with similar average carbon content without decarburization. The good combination of strength and plasticity in the compositionally gradient steel was attributed to the high strength and good plasticity provided by the core layer and decarburized layer, respectively. Additionally, the heterogeneity in the strain distribution led to an extra strain-hardening; thus, the surface layer restrains further propagation of micro-shear bands from the core layer.