The translational dynamics of poly(ethylene oxide) (PEO), in ethyl(hydroxyethyl)cellulose (EHEC) solution and in a chemically cross-linked gel of EHEC, is investigated by means of pulsed field gradient (PFG) NMR. Two different matrix concentrations of EHEC are studied, 1 and 6 wt % in which the PEO concentrations are 0.01 and 0.06 wt %, respectively. The molar mass of PEO is varied from 104 to 106, and they are fairly monodisperse (typically Mw/Mn < 1.1). The echo decays for the PEO in the 1% EHEC solution show Gaussian diffusion behavior as indicated by straight lines when the echo intensities are plotted vs the relevant parameters. This is also the case for PEO diffusing in the 6% EHEC solution matrix. For PEO diffusing in the 1% EHEC gel, a more complex situation is at hand. This is indicated by the observation of nonlinear echo decays for the PEO. The molar mass dependence of the mean-square displacement is compared to scaling relations (〈z2〉 = KM-α) and to computer simulations by Baumgärtner and Muthukumar for heterogeneous systems. For the 1% EHEC solution and gel, the 〈z2〉 dependence on the molar mass shows power law scaling with α ≈ 1. For the case when the EHEC solution matrix is 6%, a more complex behavior is seen, as revealed by a different functional form for the 〈z2〉 dependence on the molar mass. These observations are discussed in terms of polymer diffusion inside a heterogeneous matrix.