The microstructure variations of machined surface determine the performance of machined components. Accurately predicting the microstructure evolution of machined surface and thus enhancing surface hardness of machined components is an effective way to improve the service performance and realize the controllable machining of components. Machining is one the fundamental manufacturing techniques of TC4 components and the severe plastic deformation during machining process induces the complex evolutions of microstructure for TC4 machined surface. For the grain refinement phenomenon during TC4 cutting, this paper studied the multi-scale distribution characteristics of microstructure, evolution mechanisms of grain refinement and its effect on the material hardness under different cutting speeds (100 ~ 500 m/min). The results show that grain refinement degree at meso-scale (10^-6 ~ 10^-5 m) increases first and then decreases with the increasing of cutting speed. At cutting speed of 300 m/min, grain refinement degree of machined surface is 69.7% and the grains in the shear bands of chips are refined to 2 ~ 6 µm. Complex dislocation patterns and nano twining are the features of microstructure at micro-scale (10^-8 ~ 10^-7 m). The deformation twinning type is mainly characterized as {1011} compression twinning and it is generated at higher cutting speed (> 200 m/min). Grain refinement during machining of TC4 was predicted based on the modified Z-H grain refinement model and nano twining volume fraction prediction model. The hardening effect of grain refinement was also considered in the prediction model. The evolution of grain sizes and the work hardening was predicted. The relation between grain refinement and material hardness was established, and the hardness of TC4 machined surface was predicted with directional controlling the grain refinement degree and formation of nano twinning. And the hardening mechanism in microscale of TC4 machined surface was revealed.