Respiratory infectious diseases are the third cause of worldwide death. The nasopharynx is the portal of entry and the ecological niche of many microorganisms, of which some are pathogenic to humans, such as Neisseria meningitidis and Moraxella catarrhalis. These microbes possess several surface structures that interact with the actors of the innate immune system. In our attempt to understand the past evolution of these bacteria and their adaption to the nasopharynx, we first studied differences in cell wall structure, one of the strongest immune-modulators. We were able to show that a modification of peptidoglycan (PG) composition (increased proportion of pentapeptides) and a cell shape change from rod to cocci had been selected for along the past evolution of N. meningitidis. Using genomic comparison across species, we correlated the emergence of the new cell shape (cocci) with the deletion, from the genome of N. meningitidis ancestor, of only one gene: yacF. Moreover, the reconstruction of this genetic deletion in a bacterium harboring the ancestral version of the locus together with the analysis of the PG structure, suggest that this gene is coordinating the transition from cell elongation to cell division. Accompanying the loss of yacF, the elongation machinery was also lost by several of the descendants leading to the change in the PG structure observed in N. meningitidis. Finally, the same evolution was observed for the ancestor of M. catarrhalis. This suggests a strong selection of these genetic events during the colonization of the nasopharynx. This selection may have been forced by the requirement of evolving permissive interaction with the immune system, the need to reduce the cellular surface exposed to immune attacks without reducing the intracellular storage capacity, or the necessity to better compete for adhesion to target cells.