Reductive genomic evolution, driven by genetic drift, is common in endosymbiotic bacteria. Genome reduction is less common in free-living organisms, but it has occurred in the numerically dominant open-ocean bacterioplankton Prochlorococcus and "Candidatus Pelagibacter," and in these cases the reduction appears to be driven by natural selection rather than drift. Gene loss in free-living organisms may leave them dependent on cooccurring microbes for lost metabolic functions. We present the Black Queen Hypothesis (BQH), a novel theory of reductive evolution that explains how selection leads to such dependencies; its name refers to the queen of spades in the game Hearts, where the usual strategy is to avoid taking this card. Gene loss can provide a selective advantage by conserving an organism's limiting resources, provided the gene's function is dispensable. Many vital genetic functions are leaky, thereby unavoidably producing public goods that are available to the entire community. Such leaky functions are thus dispensable for individuals, provided they are not lost entirely from the community. The BQH predicts that the loss of a costly, leaky function is selectively favored at the individual level and will proceed until the production of public goods is just sufficient to support the equilibrium community; at that point, the benefit of any further loss would be offset by the cost. Evolution in accordance with the BQH thus generates "beneficiaries" of reduced genomic content that are dependent on leaky "helpers," and it may explain the observed nonuniversality of prototrophy, stress resistance, and other cellular functions in the microbial world.