The majority of viruses within the gut are obligate bacterial viruses known as bacteriophages (phages). Their bacteriotropism underscores the study of phage ecology in the gut, where they modulate and coevolve with gut bacterial communities. Traditionally, these ecological and evolutionary questions were investigated empirically via in vitro experimental evolution and, more recently, in vivo models were adopted to account for physiologically relevant conditions of the gut. Here, we probed beyond conventional phage–bacteria coevolution to investigate potential tripartite evolutionary interactions between phages, their bacterial hosts, and the mammalian gut mucosa. To capture the role of the mammalian gut, we recapitulated a life-like gut mucosal layer using in vitro lab-on-a-chip devices (to wit, the gut-on-a-chip) and showed that the mucosal environment supports stable phage–bacteria coexistence. Next, we experimentally coevolved lytic phage populations within the gut-on-a-chip devices alongside their bacterial hosts. We found that while phages adapt to the mucosal environment via de novo mutations, genetic recombination was the key evolutionary force in driving mutational fitness. A single mutation in the phage capsid protein Hoc—known to facilitate phage adherence to mucus—caused altered phage binding to fucosylated mucin glycans. We demonstrated that the altered glycan-binding phenotype provided the evolved mutant phage a competitive fitness advantage over its ancestral wild-type phage in the gut-on-a-chip mucosal environment. Collectively, our findings revealed that phages—in addition to their evolutionary relationship with bacteria—are able to evolve in response to a mammalian-derived mucosal environment.