In this article, we study Nijenhuis operators on Hom-Lie algebras. We construct a graded Lie algebra (via the Hom-analog of the Frölicher-Nijenhuis bracket) whose Maurer-Cartan elements are given by Nijenhuis operators. This allows us to define the cohomology associated to a Nijenhuis operator. As an application, we study formal deformations of Nijenhuis operators that are generated by the above-defined cohomology. Finally, we introduce Hom-NS-Lie algebras as an algebraic structure behind Nijenhuis operators on Hom-Lie algebras. We provide various examples of Hom-NS-Lie algebras.