Neisseria gonorrhoeae strains with reduced susceptibility to cefixime and ceftriaxone, with minimum inhibitory concentrations (MICs) of cefixime of 0.125–0.25 μg/ml and ceftriaxone of 0.031–0.125 μg/ml, were isolated from male urethritis patients in Tokyo, Japan, in 2006. The amino acid sequences of PenA, penicillin-binding protein 2, in these strains were of two types: PenA mosaic and nonmosaic strains. In the PenA mosaic strain, some regions in the transpeptidase-encoding domain in PenA were similar to those of Neisseria perflava/sicca, Neisseria cinerea, Neisseria flavescens, Neisseria polysaccharea, and Neisseria meningitidis. In the PenA nonmosaic strain, there was a mutation of Ala-501 to Val in PenA. In addition, we performed homology modeling of PenA wild-type and mosaic strains and compared them. The results of the modeling studies suggested that reduced susceptibility to cephems such as cefixime and ceftriaxone is due to a conformational alteration of the β-lactam-binding pocket. These results also indicated that the mosaic structures and the above point mutation in PenA make a major contribution to the reduced susceptibility to cephem antibiotics.