Oxygen diffusion coefficients have been determined in ethanol-swollen poly(vinyl alcohol), PVA, gels using a technique wherein oxygen sorption is optically monitored using singlet oxygen phosphorescence. Data were recorded as a function of the extent to which the PVA chains are chemically cross-linked using glutaraldehyde. Contrary to conventional expectation, the diffusion coefficients obtained increase with an increase in the extent of cross-linking. This observation is interpreted in terms of a cross-link-dependent increase in the microscopic heterogeneity of the polymer wherein dense cross-linked domains coexist with more fluid domains. It is expected that, in the latter domains, segmental motions of the macromolecule that facilitate oxygen diffusion are more readily achieved. This model of cross-link-dependent heterogeneity is supported by the results of small-angle X-ray scattering experiments. Among other things, the data reported herein provide an informative foundation for studies of small molecule diffusion in biological cells, particularly during photoinduced cell death where the hydrogel-like nature of the cell can change due to cross-linking reactions.