At sufficiently low temperatures, condensed-matter systems tend to develop order. An exception are quantum spin-liquids, where fluctuations prevent a transition to an ordered state down to the lowest temperatures. While such states are possibly realized in two-dimensional organic compounds, they have remained elusive in experimentally relevant microscopic two-dimensional models. Here, we show by means of large-scale quantum Monte Carlo simulations of correlated fermions on the honeycomb lattice, a structure realized in graphene, that a quantum spin-liquid emerges between the state described by massless Dirac fermions and an antiferromagnetically ordered Mott insulator. This unexpected quantum-disordered state is found to be a short-range resonating valence bond liquid, akin to the one proposed for high temperature superconductors. Therefore, the possibility of unconventional superconductivity through doping arises. We foresee its realization with ultra-cold atoms or with honeycomb lattices made with group IV elements.