The knowledge about a planned system in engineering design applications is never complete. Often, a probabilistic quantification of the uncertainty arising from this missing information is warranted in order to efficiently incorporate our partial knowledge about the system and its environment into their respective models. This leads to a robust stochastic design framework where probabilistic models of excitation uncertainties and system modeling uncertainties can be introduced; the design objective is then typically related to the expected value of a system performance measure, such as reliability or expected life-cycle cost. For complex system models, this expected value can rarely be evaluated analytically and so it is often calculated using stochastic simulation techniques, which involve an estimation error and significant computational cost. An efficient framework, consisting of two stages, is presented here for the optimization in such robust stochastic design problems. The first stage implements a novel approach, called stochastic subset optimization (SSO), for iteratively identifying a subset of the original design space that has high plausibility of containing the optimal design variables. The second stage adopts some other stochastic optimization algorithm to pinpoint the optimal design variables within that subset. The focus is primarily on the theory and implementation issues for SSO but also on topics related to the combination of the two different stages for overall enhanced efficiency. An illustrative example is presented that shows the efficiency of the proposed methodology; it considers the optimization of the reliability of a base-isolated structure considering future near-fault ground motions.