In this work, we define a deformation theory for the coupled Kahler-Yang-Mills equations, generalizing work of Sz,kelyhidi on constant scalar curvature Kahler metrics. We use the theory to find new solutions of the equations via deformation of the complex structure of a polarized manifold endowed with a holomorphic vector bundle. We also study the deformations of the recent examples of Keller and To nnesen-Friedman.