Bartonellae are gram-negative facultative intracellular alpha-proteobacteria from the family Bartonellaceae. The natural history of bartonellae consists of a reservoir/host, which is a vertebrate with chronic intravascular infection with sustained bacteremia, and a vector (usually an arthropod) that transfers the bacteria from the reservoir to a susceptible yet uninfected host. In order to reveal the sources and reservoirs of Bartonella infection in animals and vectors in New Caledonia, we collected the blood samples of 64 dogs, 8 cats, 30 bovines, 25 horses and 29 wild deer Cervus timorensis russa and 308 associated blood-sucking parasites (14 keds Hippobosca equina, 258 ticks (22 Rhipicephalus microplus, 235 Rhipicephalus sanguineus, and 1 Haemaphysalis longicornis), 12 fleas Ctenocephalides felis and 24 dog lice Trichodectes canis). We isolated ten strains of Bartonella: four Bartonella henselae from cats and six Bartonella chomelii from cattle. The strains were characterized by sequencing of five genes (16S, ITS, rpoB, gltA and ftsZ). The six strains isolated from cattle were close to the reference strain of B. chomelii and were, probably, imported from France with cattle of Limousin race. PCR showed that 35% of keds collected from deer and 31% of deer were infected by B. aff. schoenbuchensis; all other samples were negative. Our data confirmed that in New Caledonia, as in other regions of the world, cats are the major reservoirs of B. henselae. We also confirmed that Hippoboscidae flies may serve as the vectors of ruminant-associated bartonellae.