Time-resolved confocal microscopy and fluorescence correlation spectroscopy were used to examine the movements of fluorescently labeled HIV-virions (approximately 100 nm) added to samples of human cervical mucus. Particle-tracking analysis indicates that the motion of most virions is decreased 200-fold compared to that in aqueous solution and is not driven by typical diffusion. Rather, the time-dependence of their ensemble-averaged mean-square displacements is proportional to tau(alpha) + v(2)tau(2), describing a combination of anomalous diffusion (alpha approximately 0.3) and flow-like behavior, with tau being the lag time. We attribute the flow-like behavior to slowly relaxing mucus matrix that follows mechanical perturbations such as stretching and twisting of the sample. Further analysis of the tracks and displacements of individual virions indicates differences in the local movements among the virions, including constrained motion and infrequent jumps, perhaps due to abrupt changes in matrix structure. Changes in the microenvironments due to slow structural changes may facilitate movement of the virions, allowing them to reach the epithelial layer.