Due to their excellent biocompatibility and biodegradability, polypeptides have emerged as versatile bio-inspired scaffolds for the preparation of artificial biomaterials. In order to create self-assembled polypeptide nanoparticles with enhanced stability towards enzymatic degradation, we synthesized a series of random and block polypeptides based on lysine and α-aminoisobutyric acid (Aib) by the ring-opening polymerization of N-carboxyanhydrides (ROP NCA) of the corresponding amino acids. A conformational analysis carried out by means of FT-IR absorption and CD spectroscopies revealed a noticeable difference between random and block copolymers. In turn, the spatial organization of the polypeptide chains induced the formation of nanostructures of different types. The block copolymers self-assembled in vesicle-like structures, whereas polypeptides with randomly distributed monomers formed micelles. In contrast with the polymers with only natural amino acids, all nanoparticles based on Aib/Lys polypeptides showed strong resistance to proteolytic cleavage. The cytotoxicity and the kinetics of the cellular uptake of the prepared nanostructures were also studied. The results obtained could not only contribute to the understanding of long Aib polypeptide folding and self-assembling, but also pave the way to the design of nanomaterials with finely tuned properties in the fields of drug delivery and tissue engineering.