This paper analyzes the effects of storage facilities on optimal zonal pricing in competitive electricity markets. In particular, we propose a zonal pricing model that comprises consumers, producers, and storage facilities on a network with constrained transmission capacities. In its two limit cases, our zonal pricing model includes the reference nodal pricing model as well as the uniform pricing model with storage. To the best of our knowledge we are the first to analyze zonal pricing in the presence of storage. As our numerical results show, storage facilities do not only reduce the inter-temporal price volatility of a market, but may considerably change the inter-regional price structure. In particular, the inter-regional price volatility may increase in the presence of storage, which may imply a complete reconfiguration of optimal zonal boundaries as compared to the no-storage case. However, market participants may have an incentive to keep or implement a sub-optimal zonal design. Thus, storage facilities will in general challenge optimal congestion management with standard approaches to configure optimal price zones not always suggesting optimal solutions. Therefore, we propose a model extension that allows policy makers to determine welfare-maximizing zonal configurations, which account for the complex inter-regional price effects of storage facilities. Especially with regard to increasing storage investments, such a model may help to (at least partially) handle the described inefficiency problems regarding sub-optimal zonal designs that may challenge European or Australian zonal electricity markets in the near future.