Ubiquitin (Ub)-mediated proteasome-dependent proteolysis is critical in regulating multiple biological processes including apoptosis. We show that the unstructured BH3-only protein, NOXA, is degraded by an Ub-independent mechanism requiring 19S regulatory particle (RP) subunits of the 26S proteasome, highlighting the possibility that other unstructured proteins reported to be degraded by 20S proteasomes in vitro may be bona fide 26S proteasome substrates in vivo. A lysine-less NOXA (NOXA-LL) mutant, which is not ubiquitinated, is degraded at a similar rate to wild-type NOXA. Myeloid cell leukemia 1, but not other anti-apoptotic BCL-2 family proteins, stabilizes NOXA by interaction with the NOXA BH3 domain. Depletion of 19S RP subunits, but not alternate proteasome activator REG subunits, increases NOXA half-life in vivo. A NOXA-LL mutant, which is not ubiquitinated, also requires an intact 26S proteasome for degradation. Depletion of the 19S non-ATPase subunit, PSMD1 induces NOXA-dependent apoptosis. Thus, disruption of 26S proteasome function by various mechanisms triggers the rapid accumulation of NOXA and subsequent cell death strongly implicating NOXA as a sensor of 26S proteasome integrity.