This paper investigates the economic feasibility of power-to-gas (P2G) systems and gas storage options for both hydrogen and renewable methane. The study is based on a techno-economic model in which the net present value (NPV) method and Monte Carlo simulation of risks and price forward curves for the electricity and the gas market are used. We study three investment cases: a Base Case where the gas is directly sold in the market, a Storage & Arbitrage Case where temporal arbitrage opportunities between the electricity and the gas market are exploited, and a Storage & Balancing Case where the balancing markets (secondary reserve market for electricity, external balancing market for natural gas) are addressed. The optimal type and size of different centralized and decentralized storage facilities are determined and compared with each other. In a detailed sensitivity and cost analysis, we identify the key factors which could potentially improve the economic viability of the technological concepts assessed. We find that the P2G system used for bridging the balancing markets for power and gas cannot be operated profitably. For both, temporal arbitrage and balancing energy, pipe storage is preferred. Relatively high feed-in tariffs (100 (sic) MW-1 for hydrogen, 130 (sic) MW-1 for methane) are required to render pipe storage for P2G economically viable. (c) 2015 Elsevier Ltd. All rights reserved.