BRCA1-associated protein 1 (BAP1) can function as a tumor suppressor or oncogene depending on context, but its role in colorectal cancer (CRC) is not well understood. Here, we demonstrate that BAP1 suppresses CRC progression primarily by deubiquitinating and stabilizing von Hippel-Lindau tumor suppressor protein (pVHL). BAP1 undergoes covalent modification by ubiquitin-fold modifier 1 (UFM1) at Lys51, Lys61, Lys187, and Lys205, enhancing its interaction with pVHL and promoting pVHL stabilization. Loss of this modification through UFL1 depletion or reconstitution with a UFMylation-defective BAP1 mutant (4KR) impairs pVHL stabilization and promotes tumor progression in CRC cell line-based and patient-derived xenograft models. Clinically, down-regulation of UFL1 and BAP1 correlates with reduced pVHL level and poor prognosis in patients with CRC. These findings identify a previously unrecognized posttranslational mechanism regulating BAP1 activity and highlight UFMylation as essential for maintaining pVHL tumor-suppressive function. Targeting BAP1 UFMylation may represent a potential therapeutic strategy in CRC and other cancers with wild-type BAP1 and VHL.