We explicitly exhibit n-1=[D/2]-1 constants of motion for geodesics in the general D-dimensional Kerr-NUT-AdS rotating black hole spacetime, arising from contractions of even powers of the 2-form obtained by contracting the geodesic velocity with the dual of the contraction of the velocity with the (D-2)-dimensional Killing-Yano tensor. These constants of motion are functionally independent of each other and of the D-n+1 constants of motion that arise from the metric and the D-n=[(D+1)/2] Killing vectors, making a total of D independent constants of motion in all dimensions D. The Poisson brackets of all pairs of these D constants are zero, so geodesic motion in these spacetimes is completely integrable.