Deletion of single genes from expanded gene families in bacterial genomes often does not elicit a phenotype thus implying redundancy or functional non-essentiality of paralogous genes. The molecular mechanisms that facilitate evolutionary maintenance of such paralogs despite selective pressures against redundancy remain mostly unexplored. Here, we investigate the evolutionary, genetic, and functional interaction between the Helicobacter pylori cysteine-rich paralogs hcpG and hcpC in the context of H. pylori infection of cultured mammalian cells. We find that in natural H. pylori populations both hcpG and hcpC are maintained by positive selection in a dual genetic relationship that switches from complete redundancy during early infection, whereby ΔhcpC or ΔhcpG mutants themselves show no growth defect but a significant growth defect is seen in the ΔhcpC,ΔhcpG double mutant, to quantitative redundancy during late infection wherein the growth defect of the ΔhcpC mutant is exacerbated in the ΔhcpC,ΔhcpG double mutant although the ΔhcpG mutant itself shows no defect. Moreover, during early infection both hcpG and hcpC are essential for optimal translocation of the H. pylori HspB/GroEL chaperone, but during middle-to-late infection hcpC alone is necessary and sufficient for HspB/GroEL translocation thereby revealing the lack of functional compensation among paralogs. We propose that evolution of context-dependent differences in the nature of genetic redundancy, and function, between hcpG and hcpC may facilitate their maintenance in H. pylori genomes, and confer robustness to H. pylori growth during infection of cultured mammalian cells.