Internal motions of proteins are essential to their function. The time dependence of protein structural fluctuations is highly complex, manifesting subdiffusive, non-exponential behaviour with effective relaxation times existing over many decades in time, from ps up to ~102 s (refs 1,2,3,4). Here, using molecular dynamics simulations, we show that, on timescales from 10−12 to 10−5 s, motions in single proteins are self-similar, non-equilibrium and exhibit ageing. The characteristic relaxation time for a distance fluctuation, such as inter-domain motion, is observation-time-dependent, increasing in a simple, power-law fashion, arising from the fractal nature of the topology and geometry of the energy landscape explored. Diffusion over the energy landscape follows a non-ergodic continuous time random walk. Comparison with single-molecule experiments suggests that the non-equilibrium self-similar dynamical behaviour persists up to timescales approaching the in vivo lifespan of individual protein molecules.