Depletion interactions between colloidal particles dispersed in a fluid medium are effective inter-actions induced by the presence of other types of colloid and give rise to interesting equilibrium and non-equilibrium phase behaviour. These interactions are not instantaneous but build up in time through a diffusive collision process between the two species. We show by means of Brownian dynamics simulations that the fluctuations in the depletion force between two guest particles in a host dispersion of differently sized colloids do not decay exponentially with time, but show a power-law dependence. A simple scaling theory accurately describes the dependence of the magnitude of these fluctuations on time. The consequences in particular for the dynamics of colloidal mixtures are discussed.