The structural and functional complexity of the eukaryotic cell is interwoven with the complexity and functional diversification of many protein families. One example is the ARF-related family, a subgroup of the Ras superfamily GTPases that are implicated in many eukaryote-specific processes. The members of ARF-related family studied so far have been associated with membrane trafficking, microtubule assembly, and cilium-related functions. However, our understanding of the evolution of ARF-related family is limited. Building on a rapidly growing number of available genome and transcriptome sequences, we carried out a phylogenetically comprehensive in silico analysis of ARF-related family members. Our final dataset comprised 114 species and over 2,000 manually curated genes. Thanks to covering many of the small deeply diverged protist lineages, we could reconstruct the putative set of ancestral paralogs occurring already in the last eukaryotic common ancestor (LECA), including Arf1, Arf6, Arl1, Arl2, Arl3, Arl5, Arl6, Arl8, Arl13, Arl16, Arl17, Arl18, Arfrp1, Sar1, Sar1L, and SRβ. Evidence for a wide occurrence and ancestral origin of Arf6, Arl13 and Arl16 is presented for the first time. The distribution of the functionally uncharacterized Arl16 paralog suggests a functional connection to the cilium, as it is always missing from non-ciliated taxa. Arl17, Arl18 and Sar1L are absent from well-studied models, hence they have been missed in previous analyses and their function remains elusive. Post-LECA evolutionary innovations in the ARF-related family include frequent origin of lineage-specific paralogs, some of them exhibiting diverse novel architectures that combine the GTPase domain with a variety of other functional domains. Our results provide an additional line of evidence for a surprising complexity of the LECA and offer insights into the early evolution of the molecular systems the eukaryotic cell.