We present a new approach to first-principles molecular dynamics that combines a general and flexible interpolation method with ab initio evaluation of the potential energy surface. This hybrid approach extends significantly the domain of applicability of ab initio molecular dynamics. Use of interpolation significantly reduces the computational effort associated with the dynamics over most of the time scale of interest, while regions where potential energy surfaces are difficult to interpolate, for example near conical intersections, are treated by direct solution of the electronic Schrodinger equation during the dynamics. We demonstrate the concept through application to the nonadiabatic dynamics of collisional electronic quenching of Li(2p). Full configuration interaction is used to describe the wave functions of the ground and excited electronic states. The hybrid approach agrees well with full ab initio multiple spawning dynamics, while being more than an order of magnitude faster.