Ab initio molecular dynamics (AIMD) is a valuable technique for studying molecules and materials at finite temperatures where the nuclei evolve on potential energy surfaces obtained from accurate electronic structure calculations. In this work, a quantum computer-based AIMD method is presented. The electronic energies are calculated on a quantum computer using the variational quantum eigensolver (VQE) method. We compute the energy gradients numerically using the Hellmann-Feynman theorem, finite differences, and a correlated sampling technique. Our method only requires additional classical calculations of electron integrals for each degree of freedom, without any additional computations on a quantum computer beyond the initial VQE run. To achieve comparable accuracy, our gradient calculation method requires three to five orders of magnitude fewer measurements than other brute force methods without correlated sampling. As a proof of concept, AIMD dynamics simulations are demonstrated for the H2 molecule on IBM quantum devices. To the best of our knowledge, it is the first successful attempt to run AIMD on quantum devices for a chemical system. In addition, we demonstrate the validity of the method for larger molecules using full configuration interaction (FCI) wave functions. As quantum hardware and noise mitigation techniques continue to improve, the method can be utilized for studying larger molecular and material systems.