It is challenging to compute structure-function relationships of proteins using molecular physics. The problem arises from the exponential scaling of the computational searching and sampling of large conformational spaces. This scaling challenge is not met by today's methods, such as Monte Carlo, simulated annealing, genetic algorithms, or molecular dynamics (MD) or its variants such as replica exchange. Such methods of searching for optimal states on complex probabilistic landscapes are referred to more broadly as Explore-and-Exploit (EE), including in contexts such as computational learning, games, industrial planning, and modeling military strategies. Here, we describe a Bayesian method, called MELD, that ‘melds’ together EE approaches with externally added information that can be vague, combinatoric, noisy, intuitive, heuristic, or from experimental data. MELD is shown to accelerate physical MD simulations when using experimental data to determine protein structures; for predicting protein structures by using heuristic directives; and when predicting binding affinities of proteins from limited information about the binding site. Such Guided EE approaches might also be useful beyond proteins and beyond molecular science. WIREs Comput Mol Sci 2017, 7:e1309. doi: 10.1002/wcms.1309. For further resources related to this article, please visit the WIREs website.