The ‘oxygen paradox’ arises from the fact that oxygen, the molecule that aerobic life depends on, threatens its very existence. An oxygen-rich environment provided life on Earth with more efficient bioenergetics and, with it, the challenge of having to deal with a host of oxygen-derived reactive species capable of damaging proteins and other crucial cellular components. In this minireview, we explore recent insights into the metabolism of proteins that have been reversibly or irreversibly damaged by oxygen-derived species. We discuss recent data on the important roles played by the proteasomal and lysosomal systems in the proteolytic degradation of oxidatively damaged proteins and the effects of oxidative damage on the function of the proteolytic pathways themselves. Mitochondria are central to oxygen utilisation in the cell, and their ability to handle oxygen-derived radicals is an important and still emerging area of research. Current knowledge of the proteolytic machinery in the mitochondria, including the ATP-dependent AAA+ proteases and mitochondrial-derived vesicles, is also highlighted in the review. Significant progress is still being made in regard to understanding the mechanisms underlying the detection and degradation of oxidised proteins and how proteolytic pathways interact with each other. Finally, we highlight a few unanswered questions such as the possibility of oxidised amino acids released from oxidised proteins by proteolysis being re-utilised in protein synthesis thus establishing a vicious cycle of oxidation in cells.