Because of their range expansion across North America, coyotes (Canis latrans) now occur sympatrically with numerous other predator species, including red foxes (Vulpes vulpes). This raises several interesting ecological questions, including if and how sympatry affects the diet and gut microbiomes of coyotes and red foxes. We examined the gut microbiomes of sympatric populations of coyotes and red foxes within two different National Parks in Virginia, USA, that differ in land use, vegetation, and anthropogenic disturbance: Prince William Forest Park (PRWI) and Manassas National Battlefield Park (MANA). From 2012 to 2017, scat samples from PRWI and MANA were collected and analyzed. Polymerase Chain Reaction (PCR) amplification of a region of the mitochondrial cytochrome-b gene followed by restriction enzyme digestion of the PCR product was used to determine the origin of each scat sample. Next-Generation DNA sequencing of a hypervariable 16S rRNA gene region was used to determine gut microbiome information about the scat samples. There was no evidence for a difference between the gut microbiomes of red foxes in either location, or for a difference between the gut microbiomes of red foxes at either location and coyotes at the location with lower human disturbance, PRWI. However, the gut microbiomes of coyotes at the location with higher anthropogenic disturbances, MANA, revealed a marked change from those found in red foxes at either location and from those in coyotes at the location with lower disturbances. The gut microbiomes of coyotes subjected to greater human impact revealed clear evidence of dysbiosis, indicative of increased physiological stress and reduced health. We discuss our observations in the context of understanding anthropogenic impacts on coyote and red fox interactions. Our results suggest that physiological stress in the form of human disturbance may play an important role in the composition of the gut microbiome of coyotes, which can affect their overall health.