The stomach pathogen Helicobacter pylori utilizes two scaffold proteins, CheW and CheV1, to build critical chemotaxis arrays. Chemotaxis helps bacteria establish and maintain infection. Mutants lacking either of these chemotaxis proteins have different soft agar phenotypes: deletion of cheW creates non-chemotactic strains, while deletion of cheV1 results in 50% loss of chemotaxis. In this work, we characterized the cheV1 deletion mutant phenotype in detail. cheV1 deletion mutants had poor soft-agar migration initially, but regained migration ability over time. This improved bacterial migration was stable, suggesting a genetic suppressor phenotype, termed Che+. Whole-genome sequencing analysis of four distinct cheV1 Che+ strains revealed single nucleotide polymorphisms (SNPs) in a common gene, HPG27_252 (HP0273). These SNPs were predicted to truncate the encoded protein. To confirm the role of HPG27_252 in the cheV1 phenotype, we created a targeted deletion of HPG27_252 and found that loss of HPG27_252 enhanced soft-agar migration. HPG27_252 and CheV1 appear to interact directly, based on bacterial two-hybrid analysis. HPG27_252 is predicted to encode a 179 amino acid, 21 kDa protein annotated as a hypothetical protein. Computational analysis revealed this protein to be a remote homolog of the PilO Type IV filament membrane alignment complex protein. Although H. pylori is not known to possess Type IV filaments, our analysis showed it retains an operon of genes for homologs of PilO, PilN, and PilM, but does not possess other Type IV pili genes. Our data suggest the PilO homolog plays a role in regulating H. pylori chemotaxis and motility, suggesting new ideas about evolutionary steps for controlling migration through semi-solid media.