Although most globular proteins fold into a single stable structure, an increasing number have been shown to remodel their secondary and tertiary structures in response to cellular stimuli. State-of-the-art algorithms predict that these fold-switching proteins assume only one stable structure, missing their functionally critical alternative folds. Why these algorithms predict only one fold is unclear, but all of them infer protein structure from coevolved amino acid pairs. Here, we hypothesize that coevolutionary signatures of the unpredicted conformations of fold-switching proteins are being missed. Coevolutionary analysis methods are typically applied to protein superfamilies, which include sequence variants that both do and do not switch folds. Suspecting that single-fold variants could be masking coevolved amino acid pairs required to fold-switch, we developed an approach to analyze diverse protein superfamilies and protein subfamilies with sequences more similar to the target fold-switching sequences. This approach successfully revealed the coevolution of amino acid pairs uniquely corresponding to both conformations of 58 fold-switching proteins from distinct families. Using a set of coevolved amino acid pairs predicted by our approach, we successfully biased AlphaFold2 to predict two experimentally validated conformations of a candidate protein with an unsolved structure. The discovery of widespread dual-fold coevolution indicates that fold-switching sequences have been preserved by natural selection, suggesting that their functionalities provide evolutionary advantage and paving the way for sequence-based predictions of proteins with multiple folds and functions.