Viruses are the most common, abundant and diverse biological entities. Recent efforts in comparative genomics and in particular joint analysis of the genomes of viruses and non-viral selfish elements, such as transposons, have led to breakthroughs in our understanding of the evolution of these elements, in particular, in eukaryotes. A combination of phylogenomics with the quantitative analysis of bipartite gene-genome networks enables us to elucidate, albeit with different degrees of confidence, the origins of all major groups of viruses of eukaryotes from prokaryotic ancestors. In particular, a major class of dsDNA viruses centered around Polintoviruses (Polintons), self-replicating elements that lead a dual lifestyle as viruses and transposons. This class encompasses an extreme diversity of eukaryotic viruses including the giant viruses and their virophages as well as several groups of bacterial and archaeal viruses with icosahedral capsids and protein-primed replication. The Polintoviruses appear to be direct descendants of prokaryotic tectiviruses, thus tracing the origin of the majority of eukaryotic dsDNA viruses and transposons to a specific prokaryotic root. Comparison of the representation of different classes of viruses among prokaryotes and eukaryotes reveals an apparent paradox. Eukaryotes are hosts to a huge diversity of RNA viruses which are quite rare in prokaryotes. In contrast, the prokaryotic virosphere is dominated by dsDNA viruses. At first glance, this unexpected distribution of viruses might imply the emergence of the eukaryotic virosphere directly from the primordial RNA world. However, a detailed dissection of eukaryotic RNA viral genomes reveals a more complex picture that is best compatible with the assembly of these viruses from different prokaryotic building blocks including reverse transriptases of retroelements that could give rise to viral RN-dependent RNA polymerases. Thus, there seems to be a discontinuity between the primordial and modern RNA worlds. This scenario is compatible with the synbiogenetic model of eukaryogenesis.