Time-domain processing has a long history in seismic imaging and has always been a powerful workhorse that is routinely utilized. It generally leads to an expeditious construction of the subsurface velocity model in time, which can later be expressed in the Cartesian depth coordinates via a subsequent time-to-depth conversion. The conventional practice of such conversion is done using Dix inversion, which is exact in the case of laterally homogeneous media. For other media with lateral heterogeneity, the time-to-depth conversion involves solving a more complex system of partial differential equations (PDEs). In this study, we propose an efficient alternative for time-to-depth conversion and interval velocity estimation based on the assumption of weak lateral velocity variations. By considering only first-order perturbative effects from lateral variations, the exact system of PDEs required to accomplish the exact conversion reduces to a simpler system that can be solved efficiently in a layer-stripping (downward-stepping) fashion. Numerical synthetic and field data examples show that the proposed method can achieve reasonable accuracy and is significantly more efficient than previously proposed method with a speedup by an order of magnitude.