To improve the knowledge base of Borrelia in north Africa, we tested 257 blood samples collected from febrile patients in Oran, Algeria, between January and December 2012 for Borrelia species using flagellin gene polymerase chain reaction sequencing. A sequence indicative of a new Borrelia sp. named Candidatus Borrelia algerica was detected in one blood sample. Further multispacer sequence typing indicated this Borrelia sp. had 97% similarity with Borrelia crocidurae, Borrelia duttonii, and Borrelia recurrentis. In silico comparison of Candidatus B. algerica spacer sequences with those of Borrelia hispanica and Borrelia garinii revealed 94% and 89% similarity, respectively. Candidatus B. algerica is a new relapsing fever Borrelia sp. detected in Oran. Further studies may help predict its epidemiological importance.