We have developed a combined experimental and computational approach for understanding the conformational equilibria of opacity associated adhesin (Opa) protein binding to human carcinoembryonic cell adhesin molecule 1 (CEACAM). This binding is a flexible recognition process: although the Opa-CEACAM binding event is high-affinity and shows some specificity, the unliganded state of Opa is extremely flexible, and Opa is highly tolerant of mutations that still permit CEACAM recognition. To elucidate the nature of this binding process, we combine electron paramagnetic resonance experiments and molecular dynamics simulation as follows. Double electron electron resonance (DEER) distance measurements between Opa and CEACAM residues are used to inform molecular dynamics simulations of the Opa-CEACAM complex. We incorporate DEER measurements by adding spring potentials to the system Hamiltonian. In order to thoroughly sample the system's free energy landscape, we use a MARTINI coarse-grained model, cluster the resultant trajectories, and begin additional atomistic simulations from cluster centers. The benefits of this approach are twofold. First, we can direct DEER experiments by identifying under-determined regions of phase space. We identify these regions via a maximum-information-minimum-redundancy approach: the mutual information is computed between each pair Opa-CEACAM residue pair and the system's configuration, and then highly informative pairs are measured using DEER. Second, once the model is validated by DEER, we can use the same clustering methods to identify which conformational states and specific interactions contribute to Opa-CEACAM binding.