  In this paper, we introduce the cohomology theory of $\mathcal{O}$-operators
on Hom-associative algebras. This cohomology can also be viewed as the
Hochschild cohomology of a certain Hom-associative algebra with coefficients in
a suitable bimodule. Next, we study infinitesimal and formal deformations of an
$\mathcal{O}$-operator and show that they are governed by the above-defined
cohomology. Furthermore, the notion of Nijenhuis elements associated with an
$\mathcal{O}$-operator is introduced to characterize trivial infinitesimal
deformations.
