Sloths are genetically and physiologically divergent mammals. Phleboviruses are major arthropod-borne viruses (arboviruses) causing disease in humans and other animals globally. Sloths host arboviruses, but virus detections are scarce. A phlebovirus termed Anhanga virus (ANHV) was isolated from a Brazilian Linnaeus's two-toed sloth (Choloepus didactylus) in 1962. Here, we investigated the presence of phleboviruses in sera sampled in 2014 from 74 Hoffmann's two-toed (Choloepus hoffmanni, n = 65) and three-toed (Bradypus variegatus, n = 9) sloths in Costa Rica by broadly reactive RT-PCR. A clinically healthy adult Hoffmann's two-toed sloth was infected with a phlebovirus. Viral load in this animal was high at 8.5 × 107 RNA copies/ml. The full coding sequence of the virus was determined by deep sequencing. Phylogenetic analyses and sequence distance comparisons revealed that the new sloth virus, likely representing a new phlebovirus species, provisionally named Penshurt virus (PEHV), was most closely related to ANHV, with amino acid identities of 93.1%, 84.6%, 94.7% and 89.0% in the translated L, M, N and NSs genes, respectively. Significantly more non-synonymous mutations relative to ANHV occurred in the M gene encoding the viral glycoproteins and in the NSs gene encoding a putative interferon antagonist compared to L and N genes. This was compatible with viral adaptation to different sloth species and with micro-evolutionary processes associated with immune evasion during the genealogy of sloth-associated phleboviruses. However, gene-wide mean dN/dS ratios were low at 0.02–0.15 and no sites showed significant evidence for positive selection, pointing to comparable selection pressures within sloth-associated viruses and genetically related phleboviruses infecting hosts other than sloths. The detection of a new phlebovirus closely-related to ANHV, in sloths from Costa Rica fifty years after and more than 3,000 km away from the isolation of ANHV confirmed the host associations of ANHV-related phleboviruses with the two extant species of two-toed sloths.