Decoherence of a quantum system arising from its interaction with an environment is a key concept for understanding the transition between the quantum and classical world as well as performance limitations in quantum technology applications. The effects of large, weakly coupled environments are often described as a classical, fluctuating field whose dynamics is unaffected by the qubit, whereas a fully quantum description still implies some backaction from the qubit on the environment. Here we show direct experimental evidence for such a backaction for an electron-spin qubit in a GaAs quantum dot coupled to a mesoscopic environment of order 10(6) nuclear spins. By means of a correlation measurement technique, we detect the backaction of a single qubit-environment interaction whose duration is comparable to the qubit's coherence time, even in such a large system. We repeatedly let the qubit interact with the spin bath and measure its state. Between such cycles, the qubit is reinitialized to different states. The correlations of the measurement outcomes are strongly affected by the intermediate qubit state, which reveals the action of a single electron spin on the nuclear spins.