We consider a general gauge theory with independent generators and study the problem of gauge-invariant deformation of initial gauge-invariant classical action. The problem is formulated in terms of BV-formalism and is reduced to describing the general solution to the classical master equation. We show that such general solution is determined by two arbitrary generating functions of the initial fields. As a result, we construct in explicit form the deformed action and the deformed gauge generators in terms of above functions. We argue that the deformed theory must in general be non-local. The developed deformation procedure is applied to Abelian vector field theory and we show that it allows to derive non-Abelain Yang-Mills theory. This procedure is also applied to free massless integer higher spin field theory and leads to local cubic interaction vertex for such fields.