Ubiquitin is a common post-translational modifier and its conjugation is a key signal for proteolysis by the proteasome. Because the molecular mass of ubiquitin is larger than that of other modifiers such as phosphate, acetyl, or methyl groups, ubiquitylation not only influences biochemical signaling, but also may exert physical effects on its substrate proteins by increasing molecular volume and altering shape anisotropy. Here we show that ubiquitylation destabilizes the fold of two proteins, FKBP12 and FABP4, and that elongation of the conjugated ubiquitin chains further enhances this destabilization effect. Moreover, NMR relaxation analysis shows that ubiquitylation induces characteristic structural fluctuations in the backbone of both proteins. These results suggest that the ubiquitylation-driven structural fluctuations lead to fold destabilization of its substrate proteins. Thus, physical destabilization by ubiquitylation may facilitate protein degradation by the proteasome.