Campylobacter fetus is a venereal pathogen of cattle and sheep, and an opportunistic human pathogen. It is often assumed that C. fetus infection occurs in humans as a zoonosis through food chain transmission. Here we show that mammalian C. fetus consists of distinct evolutionary lineages, primarily associated with either human or bovine hosts. We use whole-genome phylogenetics on 182 strains from 17 countries to provide evidence that C. fetus may have originated in humans around 10,500 years ago and may have "jumped" into cattle during the livestock domestication period. We detect C. fetus genomes in 8% of healthy human fecal metagenomes, where the human-associated lineages are the dominant type (78%). Thus, our work suggests that C. fetus is an unappreciated human intestinal pathobiont likely spread by human to human transmission. This genome-based evolutionary framework will facilitate C. fetus epidemiology research and the development of improved molecular diagnostics and prevention schemes for this neglected pathogen.