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 arcmin^2), 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-alpha emitters at z>3, and five multiply-lensed galaxies. We report the detection of a new z=4.113 multiply lensed galaxy, with images that are consistent with lensing model predictions derived for the Frontier Fields. We detect C III], C IV, and He II emission in a multiply lensed galaxy at z=3.116, suggesting the likely presence of an active galactic nucleus. We also created narrow-band images from the MUSE datacube to automatically search for additional line emitters corresponding to high-redshift candidates, but we could not identify any significant detections other than those found by visual inspection. With the new redshifts, it will become possible to obtain an accurate mass reconstruction in the core of Abell S1063 through refined strong lensing modelling. Overall, our results illustrate the breadth of scientific topics that can be addressed with a single MUSE pointing. We conclude that MUSE is a very efficient instrument to observe galaxy clusters, enabling their mass modelling, and to perform a blind search for high-redshift galaxies.