In this study, molecular dynamics simulation was conducted to investigate the frictional behaviors between diamond tool and zirconium (Zr) substrates at the nanoscale. The effects of grain size on friction and wear were discussed under different sliding velocities. The simulation results showed that the friction forces had similar variation tendencies under different sliding velocities. Besides, the friction responses were stronger at high sliding velocities because of the atomic adhesion while the ploughing effect was more obvious at slower sliding velocity. Moreover, both the friction forces and the wear amounts increased with the decrease in the average grain sizes of the substrates. To explain this phenomenon, the internal mechanism was investigated by using the dislocation extract algorithm and the atomic displacement analyses. The results showed that the [0001]-oriented single crystalline substrate was prone to form continuous dislocation structures moving tangentially along the sliding direction due to the characteristic of Zr's slip systems, whereas grain boundaries conducted the deformation further into the polycrystalline substrates, increasing the contact areas and causing atomic accumulation in front, both resulted in stronger friction responses and wear. Accordingly, with the decrease in average grain sizes, the substrates experienced more severe subsurface damage and the deformation mechanism of nanocrystalline Zr had evolved from dislocation emission to grain boundary rotation and sliding.