Abstract: We propose a new detector concept, GraXe (to be pronounced as grace), to search for neutrinoless double beta decay in Xe-136. GraXe combines a popular detection medium in rare-event searches, liquid xenon, with a new, background-free material, grapheme. In our baseline design of GraXe, a sphere made of graphene-coated titanium mesh and filled with liquid xenon (LXe) enriched in the Xe-136 isotope is immersed in a large volume of natural LXe instrumented with photodetectors. Liquid xenon is an excellent scintillator, reasonably transparent to its own light. Graphene is transparent over a large frequency range, and impermeable to the xenon. Event position could be deduced from the light pattern detected in the photosensors. External backgrounds would be shielded by the buffer of natural LXe, leaving the ultra-radiopure internal volume virtually free of background. Industrial graphene can be manufactured at a competitive cost to produce the sphere. Enriching xenon in the isotope Xe-136 is easy and relatively cheap, and there is already near one ton of enriched xenon available in the world (currently being used by the EXO, KamLAND-Zen and NEXT experiments). All the cryogenic know-how is readily available from the numerous experiments using liquid xenon. An experiment using the GraXe concept appears realistic and affordable in a short time scale, and its physics potential is enormous.