Bacteroides are the most common bacteria in the human gut and they degrade many complex polysaccharides. The abundance of Bacteroides in the gut is shaped by the phages that infect and kill them. In response, bacteria alter their cell wall composition to limit phage infectivity. We have isolated and sequenced new Bacteroides isolates and phages that infect them. The bacterial genomes reflect the availability of sugars in the human gut. Bacteriophages demonstrate different approaches to overcome the bacterial defences. We demonstrate selective codon reassignment in novel isolates of beta-crAssphage, hypermutability, and novel DNA modifications in phages that infect Bacteroides fragilis and Bacteroides uniformis. We also discovered a new highly abundant Bacteroides phage unrelated to crAssphage and demonstrate its global diversity. The millions of year arms race between bacteria and their phages selects for rapid evolution of host and prey.