Akkermansia muciniphila, a prominent member of the gastrointestinal tract (GI) microbiota, uses mucins as a sole source of carbon and nitrogen. A. muciniphila is considered a next-generation probiotic because its abundance in humans positively correlates with protection from metabolic syndrome and obesity. However, A. muciniphila is intractable to genetic analysis and thus the molecular mechanisms underlying the metabolism of mucin, its colonization of the GI tract, and its impact on host physiology are poorly understood. Here, we developed and applied transposon mutagenesis to identify A. muciniphila factors important for the use of mucin and determined that mucin degradation products accumulate in internal compartments through a process that requires pili and a periplasmic protein complex. We further determined that the degradation of mucin and related proteoglycans is important for colonization of the GI by A. muciniphila but only in the context of competing microbes. In germ free mice, mucin use by A. muciniphila repressed the expression of host genes required for mevalonate and cholesterol biosynthesis in the colon, providing a molecular link between A. muciniphila metabolism of mucins, the regulation of lipid homeostasis and potential probiotic activities.