Proteins generally populate multiple structural states in solution. Transitions between these states are important for function, such as allosteric signaling and enzyme catalysis. Structures solved by X-ray crystallography provide valuable, but static, atomic resolution structural information. In contrast, cross-linking mass spectrometry (XLMS) and small angle X-ray scattering (SAXS) datasets contain information about conformational and compositional states of the system. The challenge lies in the data interpretation since the cross-links in the data often comes from multiple structural states. We have developed a novel computational method that simultaneously uncovers the set of structural states that are consistent with a given dataset (XLMS or SAXS). The input is a single atomic structure, a list of flexible residues, and an experimental dataset. The method finds multi-state models (models that specify two or more co-existing structural states) that are consistent with the data. The method was applied on multiple SAXS and XLMS datasets, including large multi-domain proteins and proteins with long disordered fragments. The applicability of the method extends to other datasets, such as 2D class averages from Electron Microscopy, and residual dipolar couplings.