Helicobacter pylori infection plays a causal role in the development of gastric mucosa-associated lymphoid tissue (MALT) lymphoma (LG-MALT) and duodenal ulcer (DU). Although many virulence factors have been associated with DU, many questions remain unanswered regarding the evolution of the infection toward this exceptional event, LG-MALT. The present study describes and compares the complexome of two H. pylori strains, strain J99 associated with DU and strain B38 associated with LG-MALT, using the two-dimensional blue native/SDS-PAGE method. It was possible to identify 90 different complexes (49 and 41 in the B38 and J99 strains, respectively); 12 of these complexes were common to both strains (seven and five in the membrane and cytoplasm, respectively), reflecting the variability of H. pylori strains. The 44 membrane complexes included numerous outer membrane proteins, such as the major adhesins BabA and SabA retrieved from a complex in the B38 strain, and also proteins from the hor family rarely studied. BabA and BabB adhesins were found to interact independently with HopM/N in the B38 and J99 strains, respectively. The 46 cytosolic complexes essentially comprised proteins involved in H. pylori physiology. Some orphan proteins were retrieved from heterooligomeric complexes, and a function could be proposed for a number of them via the identification of their partners, such as JHP0119, which may be involved in the flagellar function. Overall, this study gave new insights into the membrane and cytoplasm structure, and those which could help in the design of molecules for vaccine and/or antimicrobial agent development are highlighted.