The Standard Model of particle physics cannot explain the dominance of matter over anti-matter in our Universe. In many model extensions this is a very natural consequence of neutrinos being their own anti-particles (Majorana particles) which implies that a lepton number violating radioactive decay named neutrinoless double beta ($0 ubetabeta$) decay should exist. The detection of this extremely rare hypothetical process requires utmost suppression of any kind of backgrounds. The GERDA collaboration searches for $0 ubetabeta$ decay of $^{76}$Ge ($^{76}rm{Ge} rightarrow,^{76}rm{Se} + 2e^-$) by operating bare detectors made from germanium with enriched $^{76}$Ge fraction in liquid argon. Here, we report on first data of GERDA Phase II. A background level of $approx10^{-3}$ cts/(keV$cdot$kg$cdot$yr) has been achieved which is the world-best if weighted by the narrow energy-signal region of germanium detectors. Combining Phase I and II data we find no signal and deduce a new lower limit for the half-life of $5.3cdot10^{25}$ yr at 90 % C.L. Our sensitivity of $4.0cdot10^{25}$ yr is competitive with the one of experiments with significantly larger isotope mass. GERDA is the first $0 ubetabeta$ experiment that will be background-free up to its design exposure. This progress relies on a novel active veto system, the superior germanium detector energy resolution and the improved background recognition of our new detectors. The unique discovery potential of an essentially background-free search for $0 ubetabeta$ decay motivates a larger germanium experiment with higher sensitivity.