We measured the translation diffusion coefficient (D) of nanoparticles within dilute and semidilute solutions of a semiflexible polymer, xanthan. Our results showed that for particle diameters (d) of 5 and 10 nm, the obstruction theory can explain the concentration (c) dependence of D in the dilute regime. Diffusion in semidilute solutions is better explained by additionally considering the modified Darcy flow with the hydrodynamic screening length varying according to kappa approximate to c(-0.76). The depletion effect is operative for larger particles (d = 30 nm) within semidilute solutions. We used a scaling relation for the depletion layer thickness delta approximate to xi(nu), where xi is the static correlation length and the exponent nu approximate to 0.42 that can explain our data. This is in contrast with a flat surface, where the exponent is expected to be 1. Our results showed that in the situation, when the polymer network relaxation is much slower compared to the diffusive time-scale of particles, no single theory is capable to describe the concentration and size dependence of particle mobility.