The effects of a randomly moving environment on a randomly growing interface are studied by the field theoretic renormalization group. The kinetic roughening of an interface is described by the Kardar–Parisi–Zhang (KPZ) stochastic differential equation while the velocity field of the moving medium is modelled by the Navier–Stokes equation with an external random force. It is found that the large-scale, long-time (infrared) asymptotic behavior of the system is described by four non-equilibrium universality classes associated with possible fixed points of the renormalization group equations. In addition to the previously known regimes of asymptotic behavior (ordinary diffusion, kinetic growth, and passively advected scalar field), a new nontrivial regime (non-equilibrium universality class) is found. That regime corresponds to a process in which the motion of the environment and the nonlinearity of the KPZ equation are important simultaneously. The fixed points coordinates, their regions of stability and the critical exponents are calculated to the first order of the expansion in (one-loop approximation). However, the new fixed point is either infrared repulsive (d  >  2) or corresponds to imaginary coupling constant (d  <  2). Possible physical interpretation in terms of mapping to certain reaction-diffusion models and Bose systems is discussed.