Eukaryotic cells possess a remarkably diverse range of organelles that provide compartmentalization for distinct cellular functions and are likely responsible for the remarkable success of these organisms. The origins and subsequent elaboration of these compartments represent a key aspect in the transition between prokaryotic and eukaryotic cellular forms. The protein machinery required to build, maintain, and define many membrane-bound compartments is encoded by several paralog families, including small GTPases, coiled-bundle proteins, and proteins with β-propeller and α-solenoid secondary structures. Together these proteins provide the membrane coats and control systems to structure and coordinate the endomembrane system. Mechanistically and evolutionarily, they unite not only secretory and endocytic organelles but also the flagellum and nucleus. The ancient origins for these families have been revealed by recent findings, providing new perspectives on the deep evolutionary processes and relationships that underlie eukaryotic cell structure.