Bartonella species are responsible for chronic bacteremia in domestic cats, which raises a question about the antiquity of the relationship between Bartonella species and cats that act as reservoirs for the organism. The sequencing of Bartonella pap31 and groEL genes from the dental pulp of cats dating from the 13th to 16th centuries identified the presence of B. henselae genotype Houston; the observation of a unique mutation in the results of PCR assays for Bartonella species ruled out modern DNA contamination of the dental pulp samples. We conclude that cats had bacteremia due to B. henselae 800 years ago.