  $\mathcal{O}$-operators are important in broad areas in mathematics and
physics, such as integrable systems, the classical Yang-Baxter equation,
pre-Lie algebras and splitting of operads. In this paper, a deformation theory
of $\mathcal{O}$-operators is established in consistence with the general
principles of deformation theories. On the one hand, $\mathcal{O}$-operators
are shown to be characterized as the Maurer-Cartan elements in a suitable
graded Lie algebra. A given $\mathcal{O}$-operator gives rise to a differential
graded Lie algebra whose Maurer-Cartan elements characterize deformations of
the given $\mathcal{O}$-operator. On the other hand, a Lie algebra with a
representation is identified from an $\mathcal{O}$-operator $T$ such that the
corresponding Chevalley-Eilenberg cohomology controls deformations of $T$, thus
can be regarded as an analogue of the Andr\'e-Quillen cohomology for the
$\mathcal{O}$-operator. Thereafter, infinitesimal and formal deformations of
$\mathcal{O}$-operators are studied. In particular, the notion of Nijenhuis
elements is introduced to characterize trivial infinitesimal deformations.
Formal deformations and extendibility of order $n$ deformations of an
$\mathcal{O}$-operator are also characterized in terms of the new cohomology
theory. Applications are given to deformations of Rota-Baxter operators of
weight 0 and skew-symmetric $r$-matrices for the classical Yang-Baxter
equation. For skew-symmetric $r$-matrices, there is an independent
Maurer-Cartan characterization of the deformations as well as an analogue of
the Andr\'e-Quillen cohomology controlling the deformations, which turn out to
be equivalent to the ones obtained as $\mathcal{O}$-operators associated to the
coadjoint representations. Finally, infinitesimal deformations of
skew-symmetric $r$-matrices and their corresponding triangular Lie bialgebras
are studied.
