In this paper, we have exterided the theorem of the velocity-dependent symmetries to nonholonomic dynamical systems. Based on the infinitesimal transformations with respect to the coordinates, we establish the determining equations and restrictive equation of the velocity-dependent system before the structure equation is obtained. The direct and the inverse issues of the velocity-dependent symmetries for the nonholonomic dynamical system is studied and the non-Noether type conserved quantity is found as the result. Finally, we give an example to illustrate the conclusion.