The mobility of polystyrene nanoparticles ranging in diameter from 300 nm to 2 μm was measured in dilute and semidilute solutions of partially hydrolyzed polyacrylamide. In this model system, the ratio of particle to polymer size controls the long-time diffusivity of nanoparticles. The particle dynamics transition from subdiffusive on short time scales to Fickian on long time scales, qualitatively similar to predictions for polymer dynamics using a Rouse model. The diffusivities extracted from the long-time Fickian regime, however, are larger than those predicted by the Stokes−Einstein equation and the bulk zero-shear viscosity and moreover do not collapse according to hydrodynamic models. The size-dependent deviations of the long-time particle diffusivities derive instead from the coupling between the dynamics of the particle and the polymer over the length scale of the particle. Although the long-time diffusivities collapse according to predictions, deviations of the short-time scaling exponents and the crossover time between subdiffusive and Fickian dynamics indicate that the particles are only partially coupled to the relaxation modes of the polymer.