Description of correct electron-nuclear couplings is crucial in modeling of nonadiabatic dynamics. Within traditional semiclassical or mixed quantum-classical dynamics, the coupling between quantum electronic states and classical nuclear trajectories is governed by nonadiabatic coupling vectors coupled to classical nuclear momenta. This enables us to develop a very powerful nonadiabatic dynamics algorithm, namely, surface hopping dynamics, which can describe the splitting of nuclear wave packets and detailed balance. Despite its efficiency and practicality, it suffers from the lack of quantum decoherence due to incorrect accounts for the electron-nuclear coupling. Here we present a new surface hopping algorithm based on the exact electron-nuclear correlation from the exact factorization of molecular wave functions. This algorithm demands comparable computational costs to existing surface hopping methods. Numerical simulations with two-state models and a multidimensional multistate realistic molecule show that the electron-nuclear coupling beyond the nonadiabatic coupling terms can describe the quantum coherence properly.