We have conducted a two-layered spectroscopic survey (1′ × 1′ ultra deep and 3′ × 3′ 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 Hubble Space Telescope (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σ). 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 [O ii] at z< 1.5 (473 objects) and Lyα 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 Lyα emitters with high Lyα equivalent widths falling in the broadbands used for the color-color selection. Along with this paper, we release the redshift and line flux catalog.