We theoretically study the diffusion of a single attractive nanoparticle (NP) in unentangled and entangled polymer melts based on combining microscopic “core-shell” and “vehicle” mechanisms in a dynamic bond percolation theory framework. A physical picture is constructed which addresses the role of chain length (N), degree of entanglement, nanoparticle size, and NPpolymer attraction strength. The nanoparticle diffusion constant is predicted to initially decrease with N due to the dominance of the core-shell mechanism, then to cross over to the vehicle diffusion regime with a weaker N dependence, and eventually plateau at large enough N. This behavior corresponds to decoupling of NP diffusivity from the macroscopic melt viscosity, which is reminiscent of repulsive NPs in entangled melts, but here it occurs for a distinct physical reason. Specifically, it reflects a crossover to a transport mechanism whereby nanoparticles adsorb on polymer chains and diffuse using them as “vehicles” over a characteristic desorption time scale. Repetition of random desorption events then leads to Fiction long time NP diffusion. Complementary simulations for a range of chain lengths and low to moderate NP-polymer attraction strengths are also performed. They allow testing of the proposed diffusion mechanisms and qualitatively support the theoretically predicted dynamic crossover behavior. When the desorption time is smaller than or comparable to the onset of entangled polymer dynamics, the NP diffusivity becomes almost chain length independent.