Subsurface geology is highly uncertain, and it is necessary to account for this uncertainty when optimizing the location of new wells. This can be accomplished by evaluating reservoir performance for a particular well configuration over multiple realizations of the reservoir and then optimizing based, for example, on expected net present value (NPV) or expected cumulative oil production. A direct procedure for such an optimization would entail the simulation of all realizations at each iteration of the optimization algorithm. This could be prohibitively expensive when it is necessary to use a large number of realizations to capture geological uncertainty. In this work, we apply a procedure that is new within the context of reservoir management—retrospective optimization (RO)—to address this problem. RO solves a sequence of optimization subproblems that contain increasing numbers of realizations. We introduce the use of k -means clustering for selecting these realizations. Three example cases are presented that demonstrate the performance of the RO procedure. These examples use particle swarm optimization (PSO) and simplex linear interpolation (SLI)-based line search as the core optimizers (the RO framework can be used with any underlying optimization algorithm, either stochastic or deterministic). In the first example, we achieve essentially the same optimum using RO as we do using a direct optimization approach, but RO requires an order of magnitude fewer simulations. The results demonstrate the advantages of cluster-based sampling over random sampling for the examples considered. Taken in total, our findings indicate that RO using cluster sampling represents a promising approach for optimizing well locations under geological uncertainty.