Human ehrlichiosis are scantily documented in Uruguay. The aim of this study was to investigate the presence of Ehrlichia spp. in Haemaphysalis juxtakochi and in a gray brocket deer (Mazama gouazoubira) from Uruguay. The presence of Ehrlichia DNA was investigated in free-living H. juxtakochi in five localities of southeast and northeast Uruguay, as well as blood, spleen, and ticks retrieved from a M. gouazoubira. Ehrlichia spp. DNA was detected in six out of 99 tick pools from vegetation, in the spleen of M. gouazoubira, and in one out of five pools of ticks feeding on this cervid. Bayesian inference analyses for three loci (16S rRNA, dsb, and groEL) revealed the presence of a new rickettsial organism, named herein as “Candidatus Ehrlichia pampeana”. This new detected Ehrlichia is phylogenetically related to those found in ticks from Asia, as well as Ehrlichia ewingii from USA and Cameroon. Although the potential pathogenicity of “Ca. E. pampeana” for humans is currently unknown, some eco-epidemiological factors may be relevant to its possible pathogenic role, namely: (i) the phylogenetic closeness with the zoonotic agent E. ewingii, (ii) the evidence of H. juxtakochi parasitizing humans, and (iii) the importance of cervids as reservoirs for zoonotic Ehrlichia spp. The molecular detection of “Ca. E. pampeana” represents the third Ehrlichia genotype described in Uruguay.