Isolation of a Rochalimaea-like organism from a febrile patient infected with human immunodeficiency virus was confirmed. Analysis of 16S rRNA gene sequences, together with polymerase chain reaction and restriction endonuclease length polymorphism analysis of a portion of the citrate synthase gene, demonstrated that the agent is closely related to members of the genus Rochalimaea and that the isolate is genotypically identical to the presumptive etiologic agent of bacillary angiomatosis. However, the same genotypic analyses readily differentiated the new isolate from isolates of other recognized Rochalimaea species as well as other genera of bacteria previously suggested as putative etiologic agents of bacillary angiomatosis and related syndromes. We propose that the novel species be referred to as Rochalimaea henselae sp. now.