We propose a novel method for velocity estimation that leverages the newest advances in Deep Learning (DL) technology. This method is fully automatic and maps seismic shot-domain data to corresponding depth-domain velocity fields via two neural networks. Our new method is conceptually different from conventional methods such as seismic tomography or Full Waveform Inversion (FWI) that minimize a fixed objective function. Here, a system of neural networks automatically and continuously learns an objective function while training the seismic-to-velocity mapping. The newly introduced method avoids many of the drawbacks of conventional velocity estimation techniques, such as dependence on initial models or cycle-skipping. It uses the full seismic wavefield and avoids picking of first-arrival traveltimes. The system needs to be trained with hundreds or thousands of examples of seismic data paired with their corresponding velocity models relevant for the current project. Training the system is the main computationally demanding step and produces a mapping function that contains the seismic “know-how” for the presumed geologic setting. The computational cost of the subsequent estimation of velocity from new seismic data is negligent. Our first tests on complex two-dimensional synthetic data produce impressive results, underlining the potential of DL for velocity analysis.