Hamilton's inclusive fitness theory provides a leading explanation for the problem of cooperation. A general result from inclusive fitness theory is that, except under restrictive conditions, cooperation should not be subject to frequency-dependent selection. However, several recent studies in microbial systems have demonstrated that the relative fitness of cheaters, which do not cooperate, is greater when cheaters are rarer. Here we demonstrate theoretically that such frequency-dependent selection can occur in microbes when there is (1) sufficient population structuring or (2) an association between the level of cooperation and total population growth. We test prediction (2) and its underlying assumption, using the pathogenic bacterium Pseudomonas aeruginosa, by competing strains that produce iron-scavenging siderophore molecules (cooperators) with nonproducers (cheaters) at various ratios, under conditions that minimize population structuring. We found that both the relative fitness of cheaters and the productivity of the mixed culture were significantly negatively related to initial cheater frequency. Furthermore, when the period of population growth was experimentally shortened, the strength of frequency dependence was reduced. More generally, we argue that frequency-dependent selection on cooperative traits may be more common in microbes than in metazoans because strong selection, structuring, and cooperation-dependent growth will be more common in microbial populations.