This Letter reports the observation of hysteresis in the vortex pinning in a superconductor-ferromagnetic epitaxial nanocomposite consisting of fcc Gd particles incorporated in a Nb matrix. We show that this hysteretic pinning is associated with magnetic reversal losses in the Gd particles and is fundamentally different in origin to pinning interactions previously observed for ferromagnetic particles or other microstructural features.