Genomics offered the promise of transforming antibiotic discovery by revealing many new essential genes as good targets, but the results fell short of the promise. It is becoming clear that a major limitation was that essential genes for a bacterial species were often defined based on a single or limited number of strains grown under a single or limited number of in vitro laboratory conditions. In fact, the essentiality of a gene can depend on both genetic background and growth condition. We thus developed a strategy for more rigorously defining the core essential genome of a bacterial species by studying many pathogen strains and growth conditions. We assessed how many strains must be examined to converge on a set of core essential genes for a species. We used transposon insertion sequencing (Tn-Seq) to define essential genes in nine strains of Pseudomonas aeruginosa on five different media and developed a novel statistical model, FiTnEss, to classify genes as essential versus non-essential across all strain-media combinations. We defined a set of 321 core essential genes, representing 6.6% of the genome. We determined that analysis of 4 strains was typically sufficient in P. aeruginosa to converge on a set of core essential genes likely to be essential across the species across a wide range of conditions relevant to in vivo infection, and thus to represent attractive targets for novel drug discovery.