Thanks to its high sample efficiency, BO has been successful in high-cost design problems. Nonetheless, the application of BO in the literature has been restricted to low-dimensional Euclidean spaces. Along with the ever-increasing complexity and diversity of design problems, the necessity of effective BO in various spaces is increasing. In response to such demand, in this thesis, we propose BO on spaces other than low-dimensional Euclidean ones to broaden the applicability of BO. Specifically, motivated by the successes of BO with the Gaussian process (GP) surrogate model on low-dimensional Euclidean spaces, we focus on BO with the GP surrogate model. Our contributions are as follows > We propose Bayesian optimization on high-dimensional Euclidean spaces, BOCK (Chapter 3) that achieves competitive performance on problems up to 500 dimensions without making structural assumptions on the objective. > We propose Bayesian optimization on combinatorial spaces with ordinal and categorical variables, COMBO (Chapter 4) that exhibits superior sample efficiency with scalability up to a problem with 260 choices. > To model dependence between different types of variables, we propose frequency modulation (Chapter 5) and a sufficient condition for the similarity measure behavior that is crucial to BO performance on mixed-variable spaces. > We propose a batch acquisition method applicable to permutation spaces, LAW (Chapter 6) that adapts Determinantal point processes. By additionally taking into account quality with the acquisition weight, LAW scales to large batch sizes. > We show the potential of BO for combinatorial optimization problems in chip design ร macro placement (Chapter 7).