Depletion interactions between colloidal particles dispersed in a fluid medium are effective interactions induced by the presence of other types of colloid. They are not instantaneous but built up in time. We show by means of Brownian dynamics simulations that the static (mean-field) depletion force between two guest particles in a host dispersion of differently sized colloids is only approached algebraically in time. A simple scaling theory accurately describes the dependence of the magnitude of these fluctuations on time, on the inter-particle distance and on the size ratio of guest and host particles. The consequences in particular for the dynamics of colloidal mixtures are discussed.