Whole blood samples from 211 stray cats from Algiers, Algeria, were cultured to detect the presence of Bartonella species and to evaluate the genetic diversity of B. henselae strains by multiple locus VNTR analysis (MLVA). Bartonella henselae was the only species isolated from 36 (17%) of 211 cats. B. henselae genotype I was the predominant genotype (64%). MLVA typing of 259 strains from 30 bacteremic cats revealed 52 different profiles as compared to only 3 profiles using MLST. Of these 52 profiles, 48 (92.3%) were identified for the first time. One-third of the cats harbored one MLVA profile only. As there was a correlation between the age of cats and the number of MLVA profiles, we hypothesized that the single profile in these cats was the profile of the initial infecting strain. Two-third of the cats harbored 2 to 6 MLVA profiles simultaneously. The similarity of MLVA profiles obtained from the same cat, neighbor-joining clustering and structure-neighbor clustering indicate that such a diversity likely results from two different mechanisms occurring either independently or simultaneously: independent infections and genetic drift from a primary strain.