We study invariant Nijenhuis operators on a homogeneous space G/K of a semisimple Lie group G from the point of view of integrability of a system of differential equations which appear as follows. Such an operator induces an invariant symplectic form ω on the cotangent bundle T*(G/K), which is Poisson compatible with the canonical symplectic form ΩT*(G/K). This Poisson pair can be reduced to the space of G-invariant functions on T*(G/K) and produces a family of Poisson commuting functions. We give, in Lie algebraic terms, necessary and sufficient conditions of the completeness of this family. As an application we obtain two new classes of metrics on homogeneous spaces with integrable geodesic flow. (A joint work with Konrad Lompert.)