We develop a general approach to constructing a deformation that describes the mapping of any dynamical system with irreducible first-class constraints in the phase space into another dynamical system with first-class constraints. It is shown that such a deformation problem can be efficiently explored in the framework of the Batalin–Fradkin–Vilkovisky (BFV) formalism. The basic objects of this formalism are the BRST-BFV charge and a generalized Hamiltonian that satisfy the defining equations in the extended phase space in terms of (super)Poisson brackets. General solution to the deformation problem is found in terms of a (super)canonical transformation with a special generating function which is explicitly established. It is proved that this generating function is determined by a single arbitrary function which depends only on coordinates of initial dynamical system. In general, such a function must be non-local, but the deformed theory may nevertheless have a local sector. To illustrate the developed approach, we have constructed a non-local deformation of the Abelian gauge theory into a non-local non-Abelian gauge theory whose local sector coincides with the standard Yang–Mills theory.