Mucus secretions typically protect exposed surfaces of the eyes and respiratory, gastrointestinal and female reproductive tracts from foreign entities, including pathogens and environmental ultrafine particles. We hypothesized that excess exposure to some foreign particles, however, may cause disruption of the mucus barrier. Many synthetic nanoparticles are likely to be mucoadhesive due to hydrophobic, electrostatic or hydrogen bonding interactions. We therefore sought to determine whether mucoadhesive particles (MAP) could alter the mucus microstructure, thereby allowing other foreign particles to more easily penetrate mucus. We engineered muco-inert probe particles 1 µm in diameter, whose diffusion in mucus is limited only by steric obstruction from the mucus mesh, and used them to measure possible MAP-induced changes to the microstructure of fresh human cervicovaginal mucus. We found that a 0.24% w/v concentration of 200 nm MAP in mucus induced a ~10-fold increase in the average effective diffusivity of the probe particles, and a 2- to 3-fold increase in the fraction capable of penetrating physiologically thick mucus layers. The same concentration of muco-inert particles, and a low concentration (0.0006% w/v) of MAP, had no detectable effect on probe particle penetration rates. Using an obstruction-scaling model, we determined that the higher MAP dose increased the average mesh spacing (“pore” size) of mucus from 380 nm to 470 nm. The bulk viscoelasticity of mucus was unaffected by MAP exposure, suggesting MAP may not directly impair mucus clearance or its function as a lubricant, both of which depend critically on the bulk rheological properties of mucus. Our findings suggest mucoadhesive nanoparticles can substantially alter the microstructure of mucus, highlighting the potential of mucoadhesive environmental or engineered nanoparticles to disrupt mucus barriers and cause greater exposure to foreign particles, including pathogens and other potentially toxic nanomaterials.