Genome organization and phylogenetic relationships of olive leaf yellowing-associated virus (OLYaV) with other members of the Closteroviridae family were determined. The complete coding sequence of OLYaV was obtained by high throughput sequencing of total RNA from a 35-year-old olive tree (cv. Zarzaleña) from Brazil, showing olive leaf yellowing disease and deformations in the wood. This represents the first report of OLYaV in this country. A genomic sequence of 16,700 nt containing 11 open reading frames (ORFs) was recovered, representing the complete virus coding capacity. The knowledge of the nucleotide sequence of the genome including the gene that codes the coat protein will facilitate the development of diagnostic tests, which are limited so far to PCR-based methods targeting the HSP70h gene. Interestingly, a thaumatin-like protein (ORF2), previously reported in other unassigned viruses in the Closteroviridae family, persimmon virus B and actidinia virus 1, was identified in the OLYaV genome. Phylogenetic analysis of shared proteins (ORF1a, ORF1b, HSP70h, HSP90h and CP) with all members of the Closteroviridae family provides new insight into the taxonomic position of these three closteroviruses and suggests they could represent a new genus in the family.