We present mechanical Q-factors (quality factors) of a crystalline quartz test mass with a nano-structured surface, measured in the temperature regime from 5 to 300 K. The nano-structure was a grating with a period of 2 mu m and a depth of about 0.1 mu m. Comparative measurements were performed on the plain substrate and on the structured test mass with different numbers of SiO2/Ta2O5 coating layers. The measurements at different stages of the test mass fabrication process show that the surface distortion induced by the nanostructure does not severely lower the mechanical Q-factor of the substrate. Damping due to a multi-layer coating stack was found to be orders of magnitude higher. The results provide vital information concerning the potential usage of low-thermal noise nano-structured test masses in future generations of high-precision laser interferometers and in current attempts to measure quantum effects of macroscopic mirror oscillators.