We develop a new phase space method for reconstructing the index of refraction of a medium from travel time measurements. The method is based on the so-called StefanovUhlmann identity which links two Riemannian metrics with their travel time information. We design a numerical algorithm to solve the resulting inverse problem. The new algorithm is a hybrid approach that combines both Lagrangian and Eulerian formulations. In particular the Lagrangian formulation in phase space can take into account multiple arrival times naturally, while the Eulerian formulation for the index of refraction allows us to compute the solution in physical space. Numerical examples including isotropic metrics and the Marmousi synthetic model are shown to validate the new method.