Summary: Stochastic discrete resource allocation problems are difficult to solve. In this paper, we propose a new algorithm designed specifically to tackle them. The algorithm combines with the nested partitions method, the ordinal optimization techniques, and an efficient simulation control technique. The resulting hybrid algorithm retains the global perspective of the nested partitions method and the fast convergence properties of the ordinal optimization. Numerical reults demonstrate that the hybrid algorithm can be effectively used for many large-scale stochastic discrete optimization problems.