We have conducted a two-layered spectroscopic survey (1x1 ultra deep and 3x3 deep regions) in the Hubble Ultra Deep Field (HUDF) with the Multi Unit Spectroscopic Explorer (MUSE). The combination of a large field of view, high sensitivity, and wide wavelength coverage provides an order of magnitude improvement in spectroscopically confirmed redshifts in the HUDF; i.e., 1206 secure spectroscopic redshifts for HST continuum selected objects, which corresponds to 15% of the total (7904). The redshift distribution extends well beyond z>3 and to HST/F775W magnitudes as faint as ~30 mag (AB, 1-sigma). In addition, 132 secure redshifts were obtained for sources with no HST counterparts that were discovered in the MUSE data cubes by a blind search for emission-line features. In total, we present 1338 high quality redshifts, which is a factor of eight increase compared with the previously known spectroscopic redshifts in the same field. We assessed redshifts mainly with the spectral features [OII] at z<1.5 (473 objects) and Lya at 2.9<z<6.7 (692 objects). With respect to F775W magnitude, a 50% completeness is reached at 26.5 mag for ultra deep and 25.5 mag for deep fields, and the completeness remains >~20% up to 28-29 mag and ~27 mag, respectively. We used the determined redshifts to test continuum color selection (dropout) diagrams of high-z galaxies. The selection condition for F336W dropouts successfully captures ~80% of the targeted z~2.7 galaxies. However, for higher redshift selections (F435W, F606W, and F775W dropouts), the success rates decrease to ~20-40%. We empirically redefine the selection boundaries to make an attempt to improve them to ~60%. The revised boundaries allow bluer colors that capture Lya emitters with high Lya equivalent widths falling in the broadbands used for the color-color selection. Along with this paper, we release the redshift and line flux catalog.