First-principles molecular dynamics (FPMD) is a simulation method that combines molecular dynamics with the accuracy of a quantum mechanical description of electronic structure. It is increasingly used to address problems of structure determination, statistical mechanics, and electronic structure of solids, liquids and nanoparticles. The high computational cost of this approach makes it a good candidate for use on large-scale computers. In order to achieve high performance on terascale and petascale computers, current FPMD algorithms have to be reexamined and redesigned. We present new, large-scale parallel algorithms developed for FPMD simulations on computers including O(103) to O(104) CPUs. Examples include the problem of simultaneous diagonalization of symmetric matrices used in the calculation of Maximally Localized Wannier Functions (MLWFs), and the Orthogonal Procrustes problem that arises in the context of Born-Oppenheimer molecular dynamics simulations. Supported by NSF-OCI PetaApps through grant 0749217.