The "yerba mate" tree, Ilex paraguariensis, is a functionally dioecious crop species with economic relevance in several South American countries. We report a genomic screening accomplished through representational difference analysis (RDA) in male and female I. paraguariensis trees. The aim of the present paper was to investigate the occurrence of sex-related genomic differences in order to develop an early gender detection molecular method that could help reducing energy inputs during the "yerba mate" processing and that could be suitable for breeding programs. An intra-experiment redundancy was detected via SSCP analysis and sequence characterization. Taking together both reciprocal RDA assays, fragments isolated can be discriminated into three main categories. The first category of fragments shows spurious affinities with available deposited sequences and could be considered as specific to I. paraguariensis. The second category comprises sequences identified as organellar or ribosomal plant DNA. Sequences grouped in the third category involve clones akin to conserved domains of retrotransposons (RNaseH, integrases and/or chromodomains) from at least two distinct lineages of Ty3/Gypsy retrotransposons and one from Ty1/Copia retroelements, which in addition are associated to sex determination regions of the Solanaceae, Caricaceae and Salicaceae. A contig sequence was assembled that codes for an integrase core domain and a chromodomain. The phylogenetic analysis of the so-called IPRE (for I. paraguariensis retroelement) integrase domain indicates that it belongs to the Del lineage of the Chromoviridae. This is the first report of mobile elements isolated and detected from the "yerba mate" tree. Although RDA derived fragments, so far tested, have been retrieved from both sexes with similar sequences, association to sex related regions cannot be completely discarded. Implications of present results are further discussed.