Necessary conditions for existence of first integrals for nonholonomic mechanical systems are established. The first integrals are of a general structure. The theory is developed using the idea of integrating factors for the differential equations of motion for nonholonomic mechanical systems.