  In this work we define a deformation theory for the Coupled
K\"ahler-Yang-Mills equations in arXiv:1102.0991, generalizing work of
Sz\'ekelyhidi on constant scalar curvature K\"ahler metrics. We use the theory
to find new solutions of the equations via deformation of the complex structure
of a polarised manifold endowed with a holomorphic vector bundle. We also study
the deformations of the recent examples of Keller and T{\o}nnesen-Friedman.
