Atomistic structure search for organic/inorganic heterostructures is made complex by the many degrees of freedom and the need for accurate but costly density-functional theory (DFT) simulations. To accelerate and simplify structure determination in such heterogeneous functional materials, we developed the Bayesian Optimization Structure Search (BOSS) approach . BOSS builds N-dimensional surrogate models for the energy or property landscapes to infer global optima. The models are iteratively refined by sequentially sampling DFT data points with high information content. The uncertainty-led exploration/exploitation sampling strategy delivers global minima with modest sampling, but also ensures visits to less favorable regions of phase space to gather information on rare events and energy barriers.