Heterotypic cooperation, an interaction where two types of organisms promote each other’s fitness at a cost, is widely observed in nature. For example, legumes feed metabolites to rhizobia and are reciprocated with energetically-expensive fixed nitrogen. It is unclear why many forms of heterotypic cooperation exist, given that individuals who increase their consumption of benefits from partners and decrease their production of costly benefits will have a competitive advantage. Furthermore, extant heterotypic cooperation could have evolved over millions of years, making it difficult to retrace their evolutionary trajectories. Here, we used an engineered microbial system to examine how incipient heterotypic cooperation could evolve. The system is composed of two reproductively-isolated Saccharomyces cerevisiae strains: a red-fluorescent strain that requires lysine and releases adenine and a green-fluorescent strain that requires adenine and releases lysine. The ancestral coculture is viable, able to grow from low to high density in the absence of adenine and lysine supplements, only if the initial total cell density exceeds a minimal “viability threshold.” All cocultures rapidly evolved to improve viability by reducing the viability threshold. Furthermore, the evolved lysine auxotrophic cooperator was sufficient for this viability improvement. Deep sequencing of these evolved cooperators revealed duplication of the yeast chromosome 14. Sufficiency experiments revealed that this mutation promoted the “self-serving” trait of improved growth under the lysine-limited coculture environment. Moreover, this duplication event generated the “partner-serving” phenotype of increasing the rate of adenine release to the environment. Both these phenotypes also arose in lysine auxotrophic cooperators evolved as monocultures in lysine-limited chemostats. Thus pleiotropy, the control of multiple phenotypes by a single genetic element, can promote incipient heterotypic cooperation by creating “win-win” phenotypes.