Over the last 15 years, around a hundred very young stars have been observed in the central parsec of our Galaxy. While the presence of young stars forming one or two stellar disks at 0.1 pc from the supermassive black hole (SMBH) can be understood through star formation in accretion disks, the origin of the S stars observed a factor of 10 closer to the SMBH has remained a major puzzle. Here we show the S stars to be a natural consequence of dynamical interaction of two stellar disks at larger radii. Due to precession and Kozai interaction, individual stars achieve extremely high eccentricities at random orientation. Stellar binaries on such eccentric orbits are disrupted due to close passages near the SMBH, leaving behind a single S star on a much tighter orbit. The remaining star may be ejected from the vicinity of the SMBH, thus simultaneously providing an explanation for the observed hypervelocity stars in the Milky Way halo.