Oligomerization is a core structural feature that defines the form and function of many proteins. Most proteins form molecular complexes; however, there remains a dearth of diversity-driven structural studies investigating the evolutionary trajectory of these assemblies. Ribulose-1,5-bisphosphate carboxylase-oxygenase (RuBisCO) is one such enzyme that adopts multiple assemblies, although the origins and distribution of its different oligomeric states remain cryptic. Here, we retrace the evolution of ancestral and extant form II RuBisCOs, revealing a complex and diverse history of oligomerization. We structurally characterize a newly discovered tetrameric RuBisCO, elucidating how solvent-exposed surfaces can readily adopt new interactions to interconvert or give rise to new oligomeric states. We further use these principles to engineer and demonstrate how changes in oligomerization can be mediated by relatively few mutations. Our findings yield insight into how structural plasticity may give rise to new oligomeric states.