The Black Queen Hypothesis (BQH) was originally proposed to explain the dependence of some marine bacteria on helper organisms for protection from hydrogen peroxide (HOOH). The BQH predicts that selection for the evolutionary loss of leaky functions from individuals can produce commensal or mutualistic interactions. We demonstrated the leakiness of HOOH detoxification by complementing a HOOH-sensitive Escherichia coli mutant with a plasmid-encoded HOOH-detoxifying enzyme, KatG, and then evolving populations founded by this strain in two environments. When HOOH was absent, plasmid-carrying cells were outcompeted by plasmid-free segregants, reflecting the high cost of KatG expression. However, plasmid-carrying and plasmid-free cells coexisted for at least 1200 generations in three replicate populations evolved in the presence of HOOH, although their relative proportions fluctuated as beneficial mutations arose in one type or the other. Evolved plasmid-bearing cells reduced the cost of plasmid carriage even as they increased the rate of HOOH removal relative to the ancestor. Meanwhile, plasmid-free cells remained dependent on HOOH detoxification by the plasmid-bearing cells. These results demonstrate that partitioning of a Black Queen function can enable the stable coexistence of very similar organisms, even in this most restrictive case where the two types are competing for a single resource.