Mainly through vector transmission, domestic cats and dogs are infected by several Bartonella spp. and represent a large reservoir for human infections. This study investigated the relationship of prevalences of Bartonella infection in shelter dogs and cats and various ectoparasite species infesting them (fleas, ticks, and lice). Moreover, relationships between Bartonella infection and animal gender and age and presence of ectoparasites were analyzed. Blood samples were collected from 120 dogs and 103 cats. There were 386 ticks and 36 fleas harvested on these dogs, and 141 fleas, 4 ticks, and 2 lice harvested on these cats. Isolation/detection of Bartonella sp. was performed by culture, polymerase chain reaction (PCR), and partial sequencing. Bartonella was isolated from 21 (20.4%) cats and detected by PCR from 20 (19.4%) cats, 2 (1.7%) dogs, 55 (39%) fleas collected from cats, 28 (10%) ticks DNA samples, and 1 (2.8%) flea collected from dogs. When combining culture and PCR data, 27 cats and 55 fleas collected on cats were positive for Bartonella henselae or Bartonella clarridgeiae, but none were coinfected. Approximately half of the B. henselae isolates from 21 cats were B. henselae type I. Moreover, B. henselae, Bartonella phoceensis, Bartonella queenslandensis, Bartonella rattimassiliensis, Bartonella elizabethae DNA was detected in ticks collected from dogs and one flea was B. clarridgeiae PCR positive. This is the first report of such a wide variety of Bartonella spp. detected in Rhipicephalus sanguineus. Further studies are required to understand the relative importance of these ectoparasites to transmit Bartonella spp. in dogs and cats.