Eukaryotic cells use autophagy to recycle cellular components. During autophagy, autophagosomes deliver cytoplasmic contents to the vacuole or lysosome for breakdown. Mammalian cells regulate the dynamics of autophagy via ubiquitin-mediated proteolysis of autophagy proteins. Here, we show that the Arabidopsis thaliana Tumor necrosis factor Receptor-Associated Factor (TRAF) family proteins TRAF1a and TRAF1b (previously named MUSE14 and MUSE13, respectively) help regulate autophagy via ubiquitination. Upon starvation, cytoplasmic TRAF1a and TRAF1b translocated to autophagosomes. Knockout traf1a/b lines showed reduced tolerance to nutrient deficiency, increased salicylic acid and reactive oxygen species levels, and constitutive cell death in rosettes, resembling the phenotypes of autophagy-defective mutants. Starvation-activated autophagosome accumulation decreased in traf1a/b root cells, indicating that TRAF1a and TRAF1b function redundantly in regulating autophagosome formation. TRAF1a and TRAF1b interacted in planta with ATG6 and the RING finger E3 ligases SINAT1, SINAT2, and SINAT6 (with a truncated RING-finger domain). SINAT1 and SINAT2 require the presence of TRAF1a and TRAF1b to ubiquitinate and destabilize AUTOPHAGY PROTEIN6 (ATG6) in vivo. Conversely, starvation-induced SINAT6 reduced SINAT1- and SINAT2-mediated ubiquitination and degradation of ATG6. Consistently, SINAT1/SINAT2 and SINAT6 knockout mutants exhibited increased tolerance and sensitivity, respectively, to nutrient starvation. Therefore, TRAF1a and TRAF1b function as molecular adaptors that help regulate autophagy by modulating ATG6 stability in Arabidopsis.