We study the optimal operation and economic value of energy storage operated by a consumer who seeks to maximize long-term expected payoff (utility perceived from energy consumption minus energy cost). For a general setting that incorporates random electricity prices and the intertemporal substitution effect in energy demand, we establish a threshold structure for optimal storage operation policies through a dynamic programming approach. For an important special case with inelastic energy demand, we prove that the consumer's maximum expected payoff is piecewise linear in the storage level; under an additional assumption that both the demand and prices are deterministic, we further establish the equivalence between the optimal storage operation problem and a minimum cost flow problem. These results significantly simplify the (exact) computation of optimal threshold policies. We define the value of storage (VoS) as the consumer's net benefit obtained by optimally operating the storage. We show that if the consumer can always buy and sell electricity at the same (realized) price, then it is optimal for the consumer to use the storage only for arbitrage, and therefore the VoS does not depend on the consumer's demand.