The issue of ice accumulation at low-temperature circumstances causes multiple problems and serious damages in many civil infrastructures which substantially influence human daily life. However, despite the significant consideration in manufacturing anti-icing or icephobic surfaces, it is still demanding to design surfaces with well ice-repellent properties. Here in this study, we used all-atom molecular dynamics (MD) simulations to investigate ice shearing mechanism on atomistically smooth and nanotexture graphite substrates. We find that ice shearing strength strongly depends on ice temperature, the lattice structure of the surface substrate, the size of the surface nanotexture structure, and the depth of interdigitated water molecules. Our results indicate nanoscale surface roughness and depth of interdigitated water molecules tend to increase ice shear failure stress and for corrugated substrates, this is further raised with increasing the depth of interdigitated water molecules which is a result of strain being distributed well into the ice cube away from the interface. These results supply an in-depth understanding of the effect of surface nanotexture on ice shearing mechanism that provides useful information in designing anti-icing surfaces and provide for the first-time theoretical references in understanding the effect of surface nanotexture structure and depth of interlocked water on adhesive ice shear strength on nanotextured surfaces. Keywords: Ice, Graphene, Shear strength, Molecular dynamics simulation