H-NS is a nucleoid structuring protein and global repressor of virulence and horizontally-acquired genes in bacteria. H-NS can interact with itself or with homologous proteins, but protein family diversity and regulatory network overlap remain poorly defined. Here we present a comprehensive phylogenetic analysis that revealed deep-branching clades, dispelling the presumption that H-NS is the progenitor of varied molecular backups. With few exceptions, clades are either entirely chromosomal or entirely plasmid-encoded proteins. On chromosomes, StpA and newly discovered HlpP are core genes in specific genera, whereas Hfp and newly discovered HlpC are sporadically distributed. Six clades of H-NS plasmid proteins (Hpp) exhibit ancient and dedicated associations with plasmids, including three clades with fidelity for plasmid incompatibility groups H, F, or X. A proliferation of H-NS homologs in Erwiniaceae includes the first observation of potentially co-dependent H-NS forms. Conversely, the observed diversification of oligomerization domains may facilitate stable co-existence of divergent homologs in a genome. Transcriptomic and proteomic analysis of regulatory crosstalk in Salmonella revealed networked and hierarchical control of H-NS homologs. We also discovered that H-NS is both a repressor and activator of Salmonella Pathogenicity Island 1 gene expression, and both modes are restored by Sfh (HppH) in the absence of H-NS.