In this paper we present an algorithm for the valuation and optimal operation of natural gas storage facilities. Real options theory is used to derive nonlinear partial-integro-differential equations (PIDEs) for the valuation and optimal operating strategies. The equations are designed to incorporate a wide class of spot price models that can exhibit the same time-dependent, mean-reverting dynamics and price spikes as those observed in most energy markets. Particular attention is paid to the operational characteristics of real storage units, these characteristics include: working gas capacities, variable deliverability and injection rates and cycling limitations. We illustrate the model with a numerical example of a salt cavern storage facility that clearly shows how a gas storage facility is like a financial straddle with both put and call properties. Depending on the amount of gas in storage the relative influence of the put and call components vary.