Generic scaling laws, such as Kolmogorov’s 5/3 law, are milestone achievements of turbulence research in classical fluids. For quantum fluids such as atomic Bose–Einstein condensates, superfluid helium, and superfluid neutron stars, turbulence can also exist in the presence of a chaotic tangle of evolving quantized vortex lines. However, due to the lack of suitable experimental tools to directly probe the vortex-tangle motion, so far little is known about possible scaling laws that characterize the velocity correlations and trajectory statistics of the vortices in quantum-fluid turbulence, i.e., quantum turbulence (QT). Acquiring such knowledge could greatly benefit the development of advanced statistical models of QT. Here we report an experiment where a tangle of vortices in superfluid 4He are decorated with solidified deuterium tracer particles. Under experimental conditions where these tracers follow the motion of the vortices, we observed an apparent superdiffusion of the vortices. Our analysis shows that this superdiffusion is not due to Lévy flights, i.e., long-distance hops that are known to be responsible for superdiffusion of random walkers. Instead, a previously unknown power-law scaling of the vortex–velocity temporal correlation is uncovered as the cause. This finding may motivate future research on hidden scaling laws in QT.