We present particle tracking microrheology results on human mucins, isolated from normal surface and gland mucosa and one tumor sample, and examine the motility of Helicobacter pylori in these mucins. At 1.5% concentration human mucin solutions are purely viscous, with viscosity η (gland mucin) > η (surface mucin) > η (tumor mucin). In the presence of motile H. pylori bacteria, particle diffusion is enhanced, with diffusivity D+bac(tumor mucin) > D+bac(gland mucin) > D+bac(surface mucin). The surface and tumor mucin solutions exhibit an elastic response in the presence of bacteria. Taken together these results imply that particle diffusion and active swimming are coupled and impact the rheology of mucin solutions. Both J99 wild type (WT) and its isogenic ΔbabA/ΔsabA mutant swam well in broth or PGM solutions. However, the human mucins affected their motility differently, rendering them immotile in certain instances. The distribution of swimming speeds in human mucin solutions was broader with a large fraction of fast swimmers compared to PGM and broth. The bacteria swam fastest in the tumor mucin solution correlating with it having the lowest viscosity of all mucin solutions. Overall, these results suggest that mucins from different tissue locations and disease status differ in their microrheological properties and their effect on H. pylori motility.