Understanding gravity in the framework of quantum mechanics is one of the great challenges in modern physics. However, the lack of empirical evidence has lead to a debate on whether gravity is a quantum entity. Despite varied proposed probes for quantum gravity, it is fair to say that there are no feasible ideas yet to test its quantum coherent behavior directly in a laboratory experiment. Here, we introduce an idea for such a test based on the principle that two objects cannot be entangled without a quantum mediator. We show that despite the weakness of gravity, the phase evolution induced by the gravitational interaction of two micron size test masses in adjacent matter-wave interferometers can detectably entangle them even when they are placed far apart enough to keep Casimir-Polder forces at bay. We provide a prescription for witnessing this entanglement, which certifies gravity as a quantum coherent mediator, through simple spin correlation measurements.