All cyanobacteria contain carboxysomes, RuBisCO-encapsulating bacterial microcompartments that function as prokaryotic organelles. The two carboxysome types, alpha and beta, differ fundamentally in components, assembly, and species distribution. Alpha carboxysomes share a highly-conserved gene organization, with evidence of horizontal gene transfer from chemoautotrophic proteobacteria to the picocyanobacteria, and seem to co-assemble shells concomitantly with aggregation of cargo enzymes. In contrast, beta carboxysomes assemble an enzymatic core first, with an encapsulation peptide playing a critical role in formation of the surrounding shell. Based on similarities in assembly, and phylogenetic analysis of the pentameric shell protein conserved across all bacterial microcompartments, beta carboxysomes appear to be more closely related to the microcompartments of heterotrophic bacteria (metabolosomes) than to alpha carboxysomes, which appear deeply divergent. Beta carboxysomes can be found in the basal cyanobacterial clades that diverged before the ancestor of the chloroplast and have recently been shown to be able to encapsulate functional RuBisCO enzymes resurrected from ancestrally-reconstructed sequences, consistent with an ancient origin. Alpha and beta carboxysomes are not only distinct units of evolution, but are now emerging as genetic/metabolic modules for synthetic biology; heterologous expression and redesign of both the shell and the enzymatic core have recently been achieved.