The feasibility of combining safe permeation enhancers in a mucoadhesive particulate system for the oral delivery of peptide drugs was investigated in this study. Polyelectrolyte complex nanoparticles (NPs) were prepared by ionic interaction of spermine (SPM) with polyacrylic acid (PAA) polymer. Cytotoxicity studies in Caco-2 monolayers revealed the safety of the delivery system in the concentration range used for permeation enhancement. The cellular transport of fluorescein isothiocyanate dextran (FD4) showed higher permeation enhancing profiles of SPM-PAA NPs, as compared to SPM solution or PAA NPs prepared by ionic gelation with MgCl2 (Mg-PAA NPs). These permeation enhancing effects were associated with a reversible decrease in TEER values, suggesting a paracellular permeation pathway by reversible opening of the tight junctions. Furthermore, confocal microscopy results revealed strong association of the NPs prepared using fluorescence labeled PAA to Caco-2 cells. The permeation enhancing properties of SPM-PAA NPs were further evaluated in vivo after oral administration to rats, using FD4 and calcitonin as models of poorly permeating drugs. Confocal microscopy images of rats’ small intestine confirmed previous findings in Caco-2 cells and revealed a strong and prolonged penetration of FD4 from the mucosal to the basolateral side of the intestinal wall. In addition, the proposed NPs were efficient in improving the oral absorption of calcitonin, as evidenced by the significant and prolonged reduction of the blood calcemia in rats.