This paper focuses on the coordinated expansion planning of the integrated natural gas and electrical power systems with bi-directional energy conversion. Both the Gas-fired Power Generations (GPGs) and Power-to-Gas stations (P2Gs) are considered as the linkages between the natural gas and electric power systems. The system operation is optimized and embedded in the planning horizon. A bi-level multi-stage programming problem is formulated to minimize the investment cost plus the operational cost. The upper-level optimizes the expansion plan and determines the network topology as well as the generation capacities, while the lower-level is formulated as an optimal economic dispatch under the operational constraints given by the upper-level decision. To solve the bi-level multi-stage programming problem, a hybrid algorithm is proposed combining the modified binary particle swarm optimization (BPSO) and the interior point method (IPM). The BPSO is used for the upper-level sub-problem, and the IPM is adopted for the lower-level sub-problem. Numerical case studies have been carried out on the practical gas and electricity transmission network in western Denmark. Simulation results demonstrate the effectiveness of the proposed approach. (C) 2017 Elsevier Ltd. All rights reserved.