In our studies on particle mobility in polymer solutions, we have investigated and determined self-diffusion coefficients of nanoparticles in semidilute solutions of poly(ethylene glycol) (PEG, Mw = 6, 20, 35, and 100 kDa). Specially designed PEGylated dendrimers with well-defined sizes (dh = 3.4–11.0 nm) and with internal 19F moieties allow for background-free 19F NMR diffusion measurements. This way, we were able to assess the self-diffusion coefficients as a function of particle diameter and length scales (correlation length, tube diameter, polymer radius of gyration) with high resolution. Scaling arguments allowed us to visualize a clear crossover between particles probing a lower apparent viscosity to near macroviscosity when the nanoparticle size is comparable to the PEG polymer coil size. The same arguments are shown to correctly predict particle diffusion coefficients as a function of polymer concentration when the particles are smaller than the polymer coils.