Cells compartmentalize their biochemical functions in a variety of ways, notably by creating physical barriers that separate a compartment via membranes or proteins. Eukaryotes have a wide diversity of membrane-based compartments, many that are lineage- or tissue-specific. In recent years, it has become increasingly evident that membrane-based compartmentalization of the cytosolic space is observed in multiple prokaryotic lineages, giving rise to several types of distinct prokaryotic organelles. Endosymbionts, previously believed to be a hallmark of eukaryotes, have been described in several bacteria. Protein-based compartments, frequent in bacteria, are also found in eukaryotes. In the present review, we focus on selected intracellular compartments from each of these three categories, membrane-based, endosymbiotic and protein-based, in both prokaryotes and eukaryotes. We review their diversity and the current theories and controversies regarding the evolutionary origins. Furthermore, we discuss the evolutionary processes acting on the genetic basis of intracellular compartments and how those differ across the domains of life. We conclude that the distinction between eukaryotes and prokaryotes no longer lies in the existence of a compartmentalized cell plan, but rather in its complexity.