Using an ultra-deep, untargeted survey with the MUSE integral field spectrograph on the ESO Very Large Telescope, we obtain spectroscopic redshifts to a depth never explored before: galaxies with observed magnitudes m > 30–32. Specifically, we detect objects via Lyman-α emission at 2.9 < z < 6.7 without individual continuum counterparts in areas covered by the deepest optical/near-infrared imaging taken by the Hubble Space Telescope, the Hubble Ultra Deep Field. In total, we find more than 100 such objects in 9 square arcminutes at these redshifts, also including a number of sources that are visible only in the HST band that contains Lyman-α. Detailed HST and IRAC stacking analyses confirm the Lyman-α emission as well as the 1216 Å breaks, faint UV continua (MUV ∼ −15), and optical emission lines: these objects are the faintest spectroscopically-confirmed galaxies at high-z. The blue UV continuum slopes and measurements/limits on the equivalent widths of Lyman-α, which in some cases exceeds 300 Å, are consistent with ages < 10 Myr, metallicities < 5% solar, and stellar masses < 107–8 solar masses. The nature of these types of objects is intriguing as they could be the faint star-forming sources of Reionization and could represent the initial (strong) phase of stellar mass growth in galaxies.