We have searched for a heavy resonance decaying into a Z+jet final state in p (p) over bar collisions at a center of mass energy of 1.96 TeV at the Fermilab Tevatron collider using the D0 detector. No indication for such a resonance was found in a data sample corresponding to an integrated luminosity of 370 pb(-1). We set upper limits on the cross section times branching fraction for heavy resonance production at the 95% C.L. as a function of the resonance mass and width. The limits are interpreted within the framework of a specific model of excited quark production.