High protein stability is an important feature for proteins used as therapeutics, as diagnostics, and in basic research. We have previously employed consensus design to engineer optimized Armadillo repeat proteins (ArmRPs) for sequence-specific recognition of linear epitopes with a modular binding mode. These designed ArmRPs (dArmRPs) feature high stability and are composed of M-type internal repeats that are flanked by N- and C-terminal capping repeats that protect the hydrophobic core from solvent exposure. While the overall stability of the designed ArmRPs is remarkably high, subsequent biochemical and biophysical experiments revealed that the N-capping repeat assumes a partially unfolded, solvent-accessible conformation for a small fraction of time that renders it vulnerable to proteolysis and aggregation. To overcome this problem, we have designed new N-caps starting from an M-type internal repeat using the Rosetta software. The superior stability of the computationally refined models was experimentally verified by circular dichroism and nuclear magnetic resonance spectroscopy. A crystal structure of a dArmRP containing the novel N-cap revealed that the enhanced stability correlates with an improved packing of this N-cap onto the hydrophobic core of the dArmRP. Hydrogen exchange experiments further show that the level of local unfolding of the N-cap is reduced by several orders of magnitude, resulting in increased resistance to proteolysis and weakened aggregation. As a first application of the novel N-cap, we determined the solution structure of a dArmRP with four internal repeats, which was previously impeded by the instability of the original N-cap.