An effective method for enhancing the light outcoupling efficiency from top-emitting organic light-emitting diodes (TEOLEDs) with a nano-sized stochastic texture surface (NSTS) is suggested. The broadly distributed pitch and the randomly sized of islands in the NSTS enable the photons that are otherwise trapped to be emitted over the broad emission wavelength range. The NSTS-embedded TEOLEDs have wide angular-dependent emission characteristics and an enhanced external quantum efficiency (EQE). Theoretical and full-wave optical calculations were performed to understand the mechanisms of the efficiency enhancement. Optimized TEOLEDs achieved a 32% EQE enhancement compared with the reference devices without the NSTS.