Energy storage can facilitate the integration of renewable energy resources by providing arbitrage and ancillary services. Jointly optimizing energy and ancillary services in a centralized electricity market reduces the system’s operating cost and enhances the profitability of energy storage systems. However, achieving these objectives requires that storage be located and sized properly. We use a bilevel formulation to optimize the location and size of energy storage systems, which perform energy arbitrage and provide regulation services. Our model also ensures the profitability of investments in energy storage by enforcing a rate of return constraint. Computational tractability is achieved through the implementation of a primal decomposition and a subgradient-based cutting-plane method. We test the proposed approach on a 240-bus model of the Western Electricity Coordinating Council system and analyze the effects of different storage technologies, rate of return requirements, and regulation market policies on energy storage participation on the optimal storage investment decisions. We also demonstrate that the proposed approach outperforms exact methods in terms of solution quality and computational performance.