We describe x-ray photon correlation spectroscopy (XPCS) experiments tracking the motion of gold nanoparticles within solutions of high-molecular-weight polystyrene. Over displacements from nanometers to tens of nanometers, the particles undergo subdiffusive motion that is dictated by the temporal evolution of the entangled polymer mesh in the immediate vicinity of the particles. The results thus provide a novel microscopic dynamical characterization of this key structural property of polymers and more broadly demonstrate the capability of XPCS-based microrheology to interrogate heterogeneous mechanical environments in nanostructured soft materials.