Major histocompatibility complex class I (MHC-I) molecules play an essential role in the cellular immune response, presenting peptides to cytotoxic T lymphocytes (CTLs) allowing the immune system to scrutinize ongoing intracellular production of proteins. In the early 1990s, immunogenicity and stability of the peptide-MHC-I (pMHC-I) complex were shown to be correlated. At that time, measuring stability was cumbersome and time consuming and only small data sets were analysed. Here, we investigate this fairly unexplored area on a large scale compared with earlier studies. A recent small-scale study demonstrated that pMHC-I complex stability was a better correlate of CTL immunogenicity than peptide-MHC-I affinity. We here extended this study and analysed a total of 5509 distinct peptide stability measurements covering 10 different HLA class I molecules. Artificial neural networks were used to construct stability predictors capable of predicting the half-life of the pMHC-I complex. These predictors were shown to predict T-cell epitopes and MHC ligands from SYFPEITHI and IEDB to form significantly more stable MHC-I complexes compared with affinity-matched non-epitopes. Combining the stability predictions with a state-of-the-art affinity predictions NetMHCcons significantly improved the performance for identification of T-cell epitopes and ligands. For the HLA alleles included in the study, we could identify distinct sub-motifs that differentiate between stable and unstable peptide binders and demonstrate that anchor positions in the N-terminal of the binding motif (primarily P2 and P3) play a critical role for the formation of stable pMHC-I complexes. A webserver implementing the method is available at www.cbs.dtu.dk/services/NetMHCstab.