In this paper, we present a planning approach for reducing the impact that failure events in the natural gas (NG) network impose on the electricity market operation. For this purpose, an efficient computational methodology based on the Monte Carlo sequential simulation approach is developed, in order to realistically simulate the annual operation of the NG network and deduce the failure events at the connection nodes of the NG-fired power plants. The failure events are then fed into a mid-term scheduling model based on the day -ahead electricity market clearing algorithm, in order to quantify their impact on electricity prices, unit commitment and dispatch, and the energy mix. An appropriate methodology on the location selection of new storage capacity in the NG network is also described, and a case study based on the combined Hellenic electric power system and NG network is used as a. test-bed for evaluating the alternative locations. (C) 2016 Elsevier Ltd. All rights reserved.