Based on molecular dynamic simulation with tensile loading, the microstructure and tensile strength of TC4 titanium alloy are studied with nanocrystalline model. By varying the grain size while keeping the grain geometry the same, the Hall–Petch relationship is observed for average flow stress with average grain size d>15 nm, where the resistance to intragranular deformation is proportional to d-0.5. For d<15 nm, however, smaller grain size leads to smaller resistance to intergranular deformation in the form of grain boundary migration and diffusion, which leads to inverse Hall–Petch relationship. The analysis of displacement vector reveals the role of grain boundaries in restricting propagation of dislocations such as 13<11‾00>, which is responsible for FCC stacking fault inside HCP grain. In the heat treatment modeling under different temperatures, the fraction of grain boundary atoms decreases and thus the maximum tensile strength increases. On the other hand, the fraction of well-ordered atom increases, which can cause growth of existing grain and nucleation of minor BCC grain from previously grain boundary region before heat treatment.