What if gravity is classical? If true, a consistent coexistence of classical gravity and quantum matter requires that gravity exhibit irreducible fluctuations. These fluctuations can mediate classical correlations, but not quantum entanglement, between the quantized motion of the gravitationally interacting matter. We use a consistent theory of quantum-classical dynamics in the Newtonian limit of gravity to show that experimentally relevant observables can conclusively test the hypothesis that gravity is classical. This can be done, for example, by letting highly coherent source masses interact with each other gravitationally, and performing precise measurements of the cross-correlation of their motion. Theory predicts a characteristic phase response that distinguishes classical gravity from quantum gravity, and from naive sources of decoherence. Such experiments are imminently viable.