First-principles calculations were used to systematically investigate the structural, electronic and half-metallic properties of newly designed quaternary Heusler compounds ZrFeVZ (Z = Al, Ga, In). The calculated results show that these three compounds have an excellent half-metallicity in their ferrimagnetic ground state. ZrFeVZ (Z = Al, Ga, In) compounds exhibit the large spin-flip gaps of 0.348 eV, 0.428 eV and 0.323 eV at their equilibrium lattice constants, respectively. The total spin magnetic moment is 2 μ_B for all the three compounds, which is in agreement with the M_t = Z_t − 18 rule. The half-metallic properties of these three compounds are quite robust to the hydrostatic and tetragonal strain, and can also be kept when the electron correlation (U) is considered. For the ZrFeVIn compound, the spin-flip band gap achieves the maximum value (0.57 eV) under a small strain. The calculated Curie temperatures based on the mean field approximation (MFA) method are 818.04 K, 826.66 K, and 751.70 K for the ZrFeVAl, ZrFeVGa, and ZrFeVIn compounds, respectively. We hope that our current work may trigger Heusler compounds containing 4d transition metal elements and with quite large spin-flip band gaps for application in future spintronics devices.