Mcl-1 is a unique Bcl-2 family member that plays crucial roles in apoptosis. Apoptosis-unrelated functions of Mcl-1 are however emerging, further justifying its tight regulation. Here we unravel a novel mechanism of Mcl-1 regulation mediated by the haplo-insufficient tumour suppressor Beclin 1. Beclin 1 negatively modulates Mcl-1 stability in a reciprocal manner whereby depletion of one leads to the stabilization of the other. This co-regulation is independent of autophagy and of their physical interaction. Both Beclin 1 and Mcl-1 are deubiquitinated and thus stabilized by binding to a common deubiquitinase, USP9X. Beclin 1 and Mcl-1 negatively modulate the proteasomal degradation of each other through competitive displacement of USP9X. The analysis of patient-derived melanoma cells and tissue samples shows that the levels of Beclin 1 decrease, while Mcl-1 levels subsequently increase during melanoma progression in a significant inter-dependent manner. The identified inverse co-regulation of Beclin 1 and Mcl-1 represents a mechanism of functional counteraction in cancer.