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.