Metronidazole (MT) is an important drug available for Helicobacter pylori infection treatment. However, in the past few years, this drug has presented effective reduction for infection control, one of the most important reasons is attributed to the reduction of retention time in the stomach environment. Mucoadhesive nanostructured polyelectrolyte complexes (nano PECs) based on chitosan (CS) and hypromellose phthalate (HP) were rationally developed using a full factorial design (21 × 21 × 31), for the incorporation of MT based on the enhancement of the antimicrobial potential against active Helicobacter pylori, in the stomach. Different mass ratios of CS:HP (w/w) were tested, reaching the most promising ratios of 1:0.1, 1:0.5, and 1:1, and two methods of polymers addition (pouring-I and drip-II) were also evaluated. From method I, the obtained particles presented a diameter in the range of 811–1293 nm (Z-average) and a polydispersity index (PDI) between 0.47 and 0.88. By method II, there was a significant reduction in diameter and PDI to 553–739 nm and 0.23 at 0.34, respectively. The drug incorporation also resulted in a reduction in the diameter and PDI of the nano PECs. All samples showed positive zeta potential, about 20 mV, and a high percentage of MT incorporation (±95%). The method factor presented a greater influence on the nano PECs characteristics. Interactions in the system constituents were indicated by the FTIR data. Nano PECs mucoadhesiveness was observed and the composition and charge density were responsible for this phenomenon. MT dissolution evaluation showed the similarity of the dissolution profiles of free and loaded MT, in which almost 100% of the drug was in the simulated gastric medium in 120 min of testing. The in vitro antimicrobial potential against H. pylori of loaded nano PECs were measured and the minimum inhibitory concentration observed for free MT was >2000 µg/mL, while for the incorporated MT lower values were observed, showing an increase in the encapsulated MT activity.