A long-standing question in the field of superconductivity is whether pairing of electrons can arise in some cases as a result of magnetic interactions instead of electron-phonon-induced interactions as in the conventional Bardeen-Cooper-Schrieffer theory. A major challenge to the idea of magnetically mediated superconductivity has been the dramatically different behaviour of the cerium and ytterbium heavy-fermion compounds. The cerium-based systems are often found to be superconducting, in keeping with a magnetic pairing scenario, but corresponding ytterbium systems, or hole analogues of the cerium systems, are not. Despite searches over two decades there has been no evidence of heavy-fermion superconductivity in an ytterbium system, casting doubt on our understanding of the electron-hole parallelism between the cerium and the ytterbium compounds. Here we present the first empirical evidence that superconductivity is indeed possible in an ytterbium-based heavy-fermion system. In particular, we observe a superconducting transition at Tc=80 mK in high-purity single crystals of YbAlB 4 in the new structural β phase. We also observe a novel type of non-Fermi-liquid state above Tc that arises without chemical doping, in zero applied magnetic field and at ambient pressure, establishing β-YbAlB4 as a unique system showing quantum criticality without external tuning. © 2008 Macmillan Publishers Limited. All rights reserved.