Understanding gravity in the framework of quantum mechanics is one of the great challenges in modern physics. Along this line, a prime question is to find whether gravity is a quantum entity subject to the rules of quantum mechanics. It is fair to say that there are no feasible ideas yet to test the quantum coherent behaviour of gravity directly in a laboratory experiment. Here, I will introduce an idea for such a test based on the principle that two objects cannot be entangled without a quantum mediator. I will 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. I will provide a prescription for witnessing this entanglement, which certifies gravity as a quantum coherent mediator, through simple correlation measurements between two spins: one embedded in each test mass. Fundamentally, the above entanglement is shown to certify the presence of non-zero off-diagonal terms in the coherent state basis of the gravitational field modes.