Understanding gravity in the framework of quantum mechanics is one of the great challenges in modern physics. However, the lack of empirical evidence has fueled debate over whether gravity is a quantum entity. Despite various proposed probes for quantum gravity, no feasible ideas yet exist to test its quantum-coherent behaviour directly in a laboratory experiment. Here, we propose a test based on the principle that two objects cannot be entangled without a quantum mediator. We show that, despite gravity's weakness, the phase evolution induced by the gravitational interaction of two micron-sized test masses in adjacent matter-wave interferometers can entangle them detectably, even when placed far enough apart to keep Casimir-Polder forces at bay. We provide a prescription for witnessing this entanglement, certifying gravity as a quantum-coherent mediator, through simple spin-correlation measurements.