Cellular homeostasis requires regulated protein degradation. The vast majority of proteins are ubiquitinated and then recognized and degraded by 26S or 30S proteasomes, which are built from a 20S proteolytic core particle (CP) and 19S regulatory particle (RP). In addition to their core subunits, proteasomes interact transiently with a network of proteins that appear to contribute to their adaptation to different cell types and contexts. Many of these dynamic interactions are poorly characterized. This talk focuses on elusive proteasome interactors, defining structures of their complexes with proteasomes and providing insights into their functional contributions.