Many bacterial species actively take up and recombine homologous DNA into their genomes, called natural competence, a trait that offers a means to identify the genetic basis of naturally occurring phenotypic variation. Here, we describe "transformed recombinant enrichment profiling" (TREP), in which natural transformation is used to generate complex pools of recombinants, phenotypic selection is used to enrich for specific recombinants, and deep sequencing is used to survey for the genetic variation responsible. We applied TREP to investigate the genetic architecture of intracellular invasion by the human pathogen Haemophilus influenzae, a trait implicated in persistence during chronic infection. TREP identified the HMW1 adhesin as a crucial factor. Natural transformation of the hmw1 operon from a clinical isolate (86-028NP) into a laboratory isolate that lacks it (Rd KW20) resulted in ~1,000-fold increased invasion into airway epithelial cells. When a distinct recipient (Hi375, already possessing hmw1 and its paralog hmw2) was transformed by the same donor, allelic replacement of hmw2AHi375 by hmw1A86-028NP resulted in a ~100-fold increased intracellular invasion rate. The specific role of hmw1A86-028NP was confirmed by mutant and western blot analyses. Bacterial self-aggregation and adherence to airway cells were also increased in recombinants, suggesting that the high invasiveness induced by hmw1A86-028NP might be a consequence of these phenotypes. However, immunofluorescence results found that intracellular hmw1A86-028NP bacteria likely invaded as groups, instead of as individual bacterial cells, indicating an emergent invasion-specific consequence of hmw1A-mediated self-aggregation.