We present the first observations of the Frontier Fields cluster Abell S1063 taken with the newly commissioned Multi Unit Spectroscopic Explorer (MUSE) integral field spectrograph. Because of the relatively large field of view (1 arcmin2), MUSE is ideal to simultaneously target multiple galaxies in blank and cluster fields over the full optical spectrum. We analysed the four hours of data obtained in the science verification phase on this cluster and measured redshifts for 53 galaxies. We confirm the redshift of five cluster galaxies, and determine the redshift of 29 other cluster members. Behind the cluster, we find 17 galaxies at higher redshift, including three previously unknown Lyman-α emitters at z>3, and five multiply-lensed galaxies...