The influence of power-law interactions on the dynamics of many-body systems far from equilibrium is much less explored than their effect on static and thermodynamic properties. To gain insight into this problem we introduce and analyze here an out-of-equilibrium deposition process in which the deposition rate of a given particle depends as a power law on the distance to previously deposited particles. This model draws its relevance from recent experimental progress in the domain of cold atomic gases, which are studied in a setting where atoms that are excited to high-lying Rydberg states interact through power-law potentials that translate into power-law excitation rates. The out-of-equilibrium dynamics of this system turns out to be surprisingly rich. It features a self-similar evolution which leads to a characteristic power-law time dependence of observables such as the particle concentration, and results in a scale invariance of the structure factor. Our findings show that in dissipative Rydberg gases out of equilibrium the characteristic distance among excitations—often referred to as the blockade radius—is not a static but rather a dynamic quantity.