First-Principles Molecular Dynamics (FPMD) methods, although powerful, are notoriously expensive computationally due to the quantum modeling of electrons. Traditional FPMD approaches have typically been limited to a few thousand atoms at most, due to O(N3) or worse solver complexity and the large amount of communication required for highly parallel implementations. Attempts to lower the complexity have often introduced uncontrolled approximations or systematic errors. Using a robust new algorithm, we have developed an O(N) complexity solver for electronic structure problems with fully controllable numerical error. Its minimal use of global communications yields excellent scalability, allowing for very accurate FPMD simulations of more than a million atoms on over a million cores. At these scales, this approach provides multiple orders of magnitude speedup compared to the standard plane-wave approach typically used in condensed matter applications, without sacrificing accuracy. This will open up entire new classes of FPMD simulations, e.g. dilute aqueous solutions.