Given a Lagrangian dynamical system with nonholonomic constraints of arbitrary order (that is, constraints involve derivatives of the coordinates of arbitrary order), Lie symmetries and their associated conserved quantities are studied. After a brief description of the equations of motion of nonholonomic dynamical systems, Lie symmetries are introduced. The infinitesimal transformations are constructed in such a way that the generators of transformations of time and generalized coordinates are functions depending on the time, the generalized coordinates and their velocities. Then, Lie symmetries are defined by using the prolongations of the vector fields describing the infinitesimal generators of the transformation. The existence of a Lie symmetry does not imply the existence of a conserved quantity, in general. A condition that guarantees the existence of a conserved quantity is shown, and its expression in coordinates is given.