Mutualistic symbioses shape the evolution of species and ecosystems and catalyze the emergence of biological complexity, yet how such symbioses first form is unclear. We show that an obligate mutualism between the yeastSaccharomyces cerevisiaeand the algaChlamydomonas reinhardtii—two model eukaryotes with very different life histories—can arise spontaneously in an environment requiring reciprocal carbon and nitrogen exchange. This capacity for mutualism is phylogenetically broad, extending to otherChlamydomonasand fungal species. Furthermore, we witnessed the spontaneous association ofChlamydomonasalgal cells physically interacting with filamentous fungi. These observations demonstrate that under specific conditions, environmental change induces free-living species to become obligate mutualists and establishes a set of experimentally tractable, phylogenetically related, synthetic systems for studying the evolution of symbiosis.