One of the hallmarks of chronic or severe oxidative stress is the accumulation of oxidized proteins, which tend to form high-molecular-weight aggregates. The major proteolytic system responsible for the removal of oxidized cytosolic and nuclear proteins is the proteasome. This complicated proteolytic system contains a core proteasomal form (20S proteasome) and several regulators. All of these components are affected by oxidative stress to various degrees. The ATP-stimulated 26S proteasome is sensitive to oxidative stress, whereas the 20S form seems to be more resistant. The nuclear proteasome selectively degrades oxidatively damaged histones in the nuclei of mammalian cells, where it is activated and regulated by automodified PARP-1 after oxidative challenge. In this brief review we highlight the proteolysis and its regulatory effects during oxidative stress.