The imaginary-time evolution of quantum states is integral to various fields, ranging from natural sciences to classical optimization or machine learning. Since simulating quantum imaginary-time evolution generally requires storing an exponentially large wave function, quantum computers are emerging as a promising platform for this task. However, variational approaches, suitable for near-term quantum computers, struggle with a prohibitive number of measurements and impractical runtimes for relevant system sizes. Here, we suggest a stochastic approach to variational quantum imaginary-time evolution, which allows a significant reduction in runtimes. Our approach allows trading off invested resources and accuracy, which makes it also suitable for ground state preparation, where simulating the exact dynamics is not required. We demonstrate the efficiency of our algorithm in simulations and show a hardware experiment performing the imaginary-time evolution of the transverse field Ising model on 27 qubits.