Time has a fundamentally different character in quantum mechanics and in general relativity. In quantum theory events unfold in a fixed order while in general relativity temporal order is influenced by the distribution of matter. When matter requires a quantum description, temporal order is expected to become non-classical-a scenario beyond the scope of current theories. Here we provide a direct description of such a scenario. We consider a thought experiment with a massive body in a spatial superposition and show how it leads to entanglement of temporal orders between time-like events. This entanglement enables accomplishing a task, violation of a Bell inequality, that is impossible under local classical temporal order; it means that temporal order cannot be described by any pre-defined local variables. A classical notion of a causal structure is therefore untenable in any framework compatible with the basic principles of quantum mechanics and classical general relativity.