We use N-body simulations to study the evolution of the orbital eccentricities of stars deposited near (<=sssim0.05 pc) the Milky Way massive black hole (MBH), starting from initial conditions motivated by two competing models for their origin: formation in a disk followed by inward migration; and exchange interactions involving a binary star. The first model predicts modest eccentricities, lower than those observed in the S-star cluster, while the second model predicts higher eccentricities than observed. The N-body simulations include a dense cluster of 10M_o stellar black holes (SBHs), expected to accumulate near the MBH by mass segregation. Perturbations from the SBHs tend to randomize the stellar orbits, partially erasing the dynamical signatures of their origin. The eccentricities of the initially highly eccentric stars evolve, in 20 Myr (the S-star lifespan), to a distribution that is consistent at the 95% level with the observed eccentricity distribution. In contrast, the eccentricities of the initially more circular orbits fail to evolve to the observed values in 20 Myr, arguing against the disk migration scenario. We find that 20%-30% of the S-stars are tidally disrupted by the MBH over their lifetimes, and that the S-stars are not likely to be ejected as hypervelocity stars outside the central 0.05 pc by close encounters with stellar black holes.