Derivative-free, multi-modal optimization problems in high dimensions are ubiquitous in science and engineering. Obtaining satisfactory solutions of high dimensional optimization problems requires many objective function evaluations. At the same time, commonly used Bayesian optimization methods are typically computationally expensive which limits the high-dimensional function approximation accuracy, leading to sub-optimal solutions. We propose, ROSA, a novel optimization algorithm based on well-known optimization techniques such as randomized optimization, simulated annealing, and surrogate optimization. ROSA is several orders of magnitude computationally more efficient than leading scalable Bayesian optimization methods, while also obtaining comparable or better solutions with as many as 4 times less objective function evaluations. We compare ROSA with a diverse set of methods on many synthetic high-dimensional benchmark functions and on real-world problems.