Recent progress in peptide synthesis simplified the synthesis of multiple N-methylation of peptides. To evaluate how multiple N-methylation affects the bioavailability of peptides, a poly alanine cyclic hexapeptide library (n = 54), varying in the number of N-methyl (N-Me) groups (1−5 groups) and their position, was synthesized. The peptides were evaluated for their intestinal permeability in vitro using the Caco-2 model. Further evaluation of the transport route of chosen analogues was performed using rat excised viable intestinal tissue, a novel colorimetric liposomal model and the parallel artificial membrane permeability assay (PAMPA). While most members were found to have poor permeability (permeability coefficient, Papp < 1 × 10−6 cm/s, lower than mannitol, the marker for paracellular permeability), 10 analogues were found to have high Caco-2 permeability, (Papp > 1 × 10−5 cm/s, similar to testosterone, a marker of transcellular permeability). No correlation was found between the number of N-methylated groups and the enhanced permeability. However, 9/10 permeable peptides in the Caco-2 model included an N-Me placed adjacently to the d-Ala position. While the exact transport route was not fully characterized, the data suggests a facilitated diffusion. It can be concluded that multiple N-methylation of peptides may improve intestinal permeability, and therefore can be utilized in the design of orally available peptide-based therapeutics.