Nanoparticle diffusion in polymer melts is studied by the combination of Molecular Dynamics (MD) simulations and Mode-Coupling Theory (MCT). In accord with earlier experimental, simulation, and theoretical studies, we find that the Stokes-Einstein (SE) hydrodynamic relation Dn ∼ 1/Rn holds when the nanoparticle radius Rn is greater than the polymer gyration radius Rg, while in the opposite regime, the measured nanoparticle diffusion coefficient Dn exceeds the SE value by as much as an order of magnitude. The MCT values of Dn are found to be consistently higher than the MD simulation values. The observed discrepancy is attributed to the approximations involved in constructing the microscopic friction as well as to the approximate forms for dynamic structure factors used in MCT. In a thorough test of underlying MCT assumptions and approximations, various structural and dynamical quantities required as input for MCT are obtained directly from MD simulations. We present the improved MCT approach, which involves splitting of the microscopic time-dependent friction into two terms: binary (originating from short-time dynamics) and collective (due to long-time dynamics). Using MD data as input in MCT, we demonstrate that the total friction is largely dominated by its binary short-time term, which, if neglected, leads to severe overestimation of Dn. As a result, the revised version of MCT, in agreement with the present MD data, predicts 1/Rn 2 scaling of the probe diffusion coefficient in a non-hydrodynamic regime when Rn < Rg. If the total friction is dominated by the collective long-time component, one would observe 1/Rn 3 scaling of Dn in accordance with previous studies.