This work presents a density functional study of neutral, cationic, and anionic sodium cluster heptamers. The cluster structures were optimized with the local density approximation as well as with the generalized gradient approximation. For the neutral and cationic clusters new unexpected isomers are found closed in energy to the well known ground state structures. In the case of the neutral heptamer the new isomer was first noticed by inspection of a first-principles Born-Oppenheimer molecular dynamics (BOMD) simulations at 300 K. A structure alignment algorithm is presented which facilitates the discovery of new structures from such BOMD simulations. With this algorithm the structural evolution of the two low-lying isomers of the neutral, cationic, and anionic heptamer was analyzed at different temperatures. This work demonstrates the capability of reasonably long (approximately 100 ps) first-principles BOMD simulations to explore the potential energy landscape of metallic clusters.