This analysis evaluates how the value of energy storage changes when adding variable generation (VG) renewable energy resources to the grid. A series of VG energy penetration scenarios from 16% to 55% were generated for a utility system in the western United States. This operational value of storage (measured by its ability to reduce system production costs) was estimated in each VG scenario, considering provision of different services and with several sensitivities to fuel price and generation mix. Overall, the results found that the presence of VG increases the value of energy storage by lowering off-peak energy prices more than on-peak prices, leading to a greater opportunity to arbitrage this price difference. However, significant charging from renewables, and consequently a net reduction in carbon emissions, did not occur until VG penetration was in the range of 40%-50%. Increased penetration of VG also increases the potential value of storage when providing reserves, mainly by increasing the amount of reserves required by the system. Despite this increase in value, storage may face challenges in capturing the full benefits it provides. Due to suppression of on-/off-peak price differentials, reserve prices, and incomplete capture of certain system benefits (such as the cost of power plant starts), the revenue obtained by storage in a market setting appears to be substantially less than the net benefit (reduction in production costs) provided to the system. Furthermore, it is unclear how storage will actually incentivize large-scale deployment of renewables needed to substantially increase VG penetration. This demonstrates some of the additional challenges for storage deployed in restructured energy markets.