Entanglement entropies calculated in the framework of quantum field theory on classical, flat or curved, spacetimes are known to show an intriguing area law in four dimensions, but they are also notorious for their quadratic ultraviolet divergences. In this paper we demonstrate that the analogous entanglement entropies when computed within the Asymptotic Safety approach to background independent quantum gravity are perfectly free from such divergences. We argue that the divergences are an artifact due to the over-idealization of a rigid, classical spacetime geometry which is insensitive to the quantum dynamics.