Developed countries increasingly rely on gas storage for security of supply. Widespread deregulation has created markets that help assign an objective value to existing and planned storages. Storage valuation is nevertheless a challenging task if we consider both the financial and physical aspects of storage. In this article, we develop a Monte Carlo valuation method, which can incorporate realistic gas price dynamics and complex physical constraints. Specifically, we extend the Least Squares Monte Carlo method for American options to storage valuation. We include numerical results and show ways to improve computational speed.