The understanding of protein-protein interaction mechanisms is key to the atomistic description of cell signaling pathways and for the development of new drugs. In this context, the mechanism of intrinsically disordered proteins folding upon binding has attracted attention. The VirB9 C-terminal domain (VirB9Ct) and the VirB7 N-terminal motif (VirB7Nt) associate with VirB10 to form the outer membrane core complex of the Type IV Secretion System injectisome. Despite forming a stable and rigid complex, VirB7Nt behaves as a random coil, while VirB9Ct is intrinsically dynamic in the free state. Here we combined NMR, stopped-flow fluorescence, and computer simulations using structure-based models to characterize the VirB9Ct-VirB7Nt coupled folding and binding mechanism. Qualitative data analysis suggested that VirB9Ct preferentially binds to VirB7Nt by way of a conformational selection mechanism at lower temperatures. However, at higher temperatures, energy barriers between different VirB9Ct conformations are more easily surpassed. Under these conditions the formation of non-native initial encounter complexes may provide alternative pathways toward the native complex conformation. These observations highlight the intimate relationship between folding and binding, calling attention to the fact that the two molecular partners must search for the most favored intramolecular and intermolecular interactions on a rugged and funnelled conformational energy landscape, along which multiple intermediates may lead to the final native state.