Protein turnover is a key aspect of cellular homeostasis and proteome dynamics. However, there is little consensus on which properties of a protein determine its lifetime in the cell. In this work, we exploit two reliable datasets of experimental protein degradation rates to learn models and uncover determinants of protein degradation, with particular focus on properties that can be derived from the sequence. Our work shows that simple sequence features suffice to obtain predictive models of which the output correlates reasonably well with the experimentally measured values. We also show that intrinsic disorder may have a larger effect than previously reported, and that the effect of PEST regions, long thought to act as specific degradation signals, can be better explained by their disorder. We also find that determinants of protein degradation depend on the cell types or experimental conditions studied. This analysis serves as a first step towards the development of more complex, mature computational models of degradation of proteins and eventually of their full life cycle.