We observe a change in the segmental dynamics of hydrogels based on hydrophobically modified ethoxylated urethanes (HEUR) when hydrophobic magnetite nanoparticles (MNPs) are embedded in the hydrogels. The dynamics of the nanocomposite hydrogels is investigated using dielectric relaxation spectroscopy (DRS) and neutron spin echo (NSE) spectroscopy. The magnetic nanoparticles within the hydrophobic domains of the HEUR polymer network increase the size of these domains and their distance. The size increase leads to a dilution of the polymers close to the hydrophobic domain, allowing higher mobility of the smallest polymer blobs close to the "center". This is reflected in the decrease of the activation energy of the β-process detected in the DRS data. The increase in distance leads to an increase of the size of the largest hydrophilic polymer blobs. Therefore, the segmental dynamics of the largest blobs is slowed down. At short time scales, i.e. 10(-9) s < τ < 10(-3) s, the suppression of the segmental dynamics is reflected in the α-relaxation processes detected in the DRS data and in the decrease of the relaxation rate Γ of the segmental motion in the NSE data with increasing concentration of magnetic nanoparticles. The stepwise (multi-stage) freezing of the small blobs is only visible for the pure hydrogel at low temperatures. On the other hand, the glass transition temperature (Tg) decreases upon increasing the MNP loading, indicating an acceleration of the segmental dynamics at long time scales (τ∼ 100 s). Therefore, it would be possible to tune the Tg of the hydrogels by varying the MNP concentration. The contribution of the static inhomogeneities to the total scattering function Sst(q) is extracted from the NSE data, revealing a more ordered gel structure than the one giving rise to the total scattering function S(q), with a relaxed correlation length ξNSE = (43 ± 5) Å which is larger than the fluctuating correlation length from a static investigation ξSANS = (17.2 ± 0.3) Å.