Dynamic flexibility is key to protein structure and function. A novel combination of single-molecule fluorescence with molecular simulations now allows us to probe this flexibility in a folded protein complex, with a surprising result. We directly observe nanometer distance fluctuations on a sub-microsecond timescale in the high-affinity complex of the intrinsically disordered interaction domains of CBP/p300 and ACTR, a p160 coactivator. The motions are only weakly coupled to solvent dynamics, but are dominated by interactions within the complex. An extension of our method to three-colors reveals that the breathing of the complex is described by a diffusion on a free energy surface with a low degree of collectivity between the coordinates. High affinity and high flexibility in folded protein complexes are therefore not mutually exclusive, particularly not for hub proteins that have evolved to bind multiple ligands.