Compacted graphite iron (CGI) is considered to be an ideal diesel engine material with excellent physical and mechanical properties, which meet the requirements of energy conservation and emission reduction. However, knowledge of the microstructure evolution of CGI and its impact on flow stress remains limited. In this study, a new modeling approach for the stress–strain relationship is proposed by considering the strain hardening effect and stored energy caused by the microstructure evolution of CGI. The effects of strain, strain rate, and deformation temperature on the microstructure of CGI during compression deformation are examined, including the evolution of graphite morphology and the microstructure of the pearlite matrix. The roundness and fractal dimension of graphite particles under different deformation conditions are measured. Combined with finite element simulation models, the influence of graphite particles on the flow stress of CGI is determined. The distributions of grain boundary and geometrically necessary dislocations (GNDs) density in the pearlite matrix of CGI under different strains, strain rates, and deformation temperatures are analyzed by electron backscatter diffraction technology, and the stored energy under each deformation condition is calculated. Results show that the proportion and amount of low-angle grain boundaries and the average GNDs density increase with the increase of strain and strain rate and decreased first and then increased with an increase in deformation temperature. The increase in strain and strain rate and the decrease in deformation temperature contribute to the accumulation of stored energy, which show similar variation trends to those of GNDs density. The parameters in the stress–strain relationship model are solved according to the stored energy under different deformation conditions. The consistency between the predicted results from the proposed stress–strain relationship and the experimental results shows that the evolution of stored energy can accurately predict the stress–strain relationship of CGI.