This paper explores the use of Random Decision Forest as a surrogate model for global optimization, providing an alternative to Gaussian process-based kriging. RDF boasts several advantages, including linear training complexity, robustness to noise, and support for categorical features. However, its piecewise-constant predictions and lack of inherent uncertainty quantification present significant challenges. In order to address these limitations, we propose four techniques for estimating uncertainty in RDF: covariance-based, intersection-based, nearest-neighbor, and quadratic approximation. Each of these techniques is adept at balancing accuracy and computational efficiency. Furthermore, a heuristic for the SEGO algorithm is introduced, which dynamically selects new evaluation points by considering both surrogate minima and high-uncertainty regions. Empirical tests on diverse function classes demonstrate the superiority of our approach in comparison to kriging. This is in terms of the optimization of speed and the quality of solutions. This approach has demonstrated notable efficacy, particularly in high-dimensional settings. The function classes encompass the following types: unimodal, ravine-like, periodic, multi-modal, and noisy.