Purpose: Multispectral imaging can provide reflectance measurements at multiple spectral bands for each image pixel. These measurements can be used for estimation of important physiological parameters, such as oxygenation, which can provide indicators for the success of surgical treatment or the presence of abnormal tissue. The goal of this work was to develop a method to estimate physiological parameters in an accurate and rapid manner suited for modern high-resolution laparoscopic images. Methods: While previous methods for oxygenation estimation are based on either simple linear methods or complex model-based approaches exclusively suited for off-line processing, we propose a new approach that combines the high accuracy of model-based approaches with the speed and robustness of modern machine learning methods. Our concept is based on training random forest regressors using reflectance spectra generated with Monte Carlo simulations. Results: According to extensive in silico and in vivo experiments, the method features higher accuracy and robustness than state-of-the-art online methods and is orders of magnitude faster than other nonlinear regression based methods. Conclusion: Our current implementation allows for near real-time oxygenation estimation from megapixel multispectral images and is thus well suited for online tissue analysis.