Polymer diffusion is enhanced when nanorods (NRs) in a polymer nanocomposite are mobile relative to nanocomposites containing immobile NRs. NR mobility is tuned by varying the molecular weight of the matrix polymer and the NR concentration, and diffusion of deuterated polystyrene (dPS) tracers with varying molecular weight is studied using elastic recoil detection. When dPS diffuses faster than the NRs such that the NRs are “immobile” on the time scale of dPS, the tracer diffusion coefficient (D) monotonically decreases as the nanorod concentration increases; we interpret these results as though the nanorods provide additional topological constraints that slow diffusion of dPS. When the tracer diffusion is slow relative to NR diffusion (i.e., “mobile” NRs), diffusion is enhanced relative to the immobile NR case. This enhanced diffusion is captured by a slip-link model with two populations of topological constraints: one fixed population attributed to the PS matrix, and a second population of constraints with a finite constraint release time determined by the diffusion time of the NRs relative to dPS. These experimental and computational results provide fundamental insights into the nature of entanglements and constraint release in NR-containing polymer nanocomposites.