Flagellar export chaperone FliS prevents premature polymerization of flagellins and is critical for flagellar assembly and bacterial colonization. Previously, a yeast 2-hybrid study identified various FliS-associated proteins in Helicobacter pylori, but the implications of these interactions are not known. Here we demonstrate the biophysical interaction of FliS (HP0753) and the uncharacterized protein HP1076 from H. pylori. HP1076 possesses a cochaperone activity that promotes the folding and chaperone activity of FliS. We further determined the crystal structures of FliS, HP1076, and the binary complex at 2.7, 1.8, and 2.7 Å resolution, respectively. HP1076 adopts a helix-rich bundle structure and interestingly shares a similar fold with a flagellin homologue, hook-associated protein, and FliS. The FliS-HP1076 complex revealed an extensive electrostatic and hydrophobic binding interface, which is distinct from the flagellin binding pocket in FliS. The helical stacking interaction between HP1076 and FliS suggests that HP1076 stabilizes 2 α helices of FliS and therefore the overall structure of the bundle. Our findings provide new insights into flagellar export chaperones and may have implications for other secretion chaperones in the type III secretion system.