Multi-energy systems have emerged as a potential solution to tackle the flexibility challenges caused by the integration of renewable energy resources. However, the uncertainty of multi-energy load growth and long-term energy cost fluctuations considerably affect the planning and deployment of such energy systems. Furthermore, the transition from fossil energy sources and traditional energy carriers, such as natural gas, to power-based systems is expected to intensify. Therefore, future energy systems planners require planning methodologies that incorporate long-term cost changes with power system analysis. Hence, this paper introduces a novel combined planning methodology. The methodology incorporates a genetic algorithm with a multistage planning approach, power-flow analysis, and multi-energy management to deliver a holistic tool for energy system planners. This tool can optimise municipal multi-energy systems across electricity, heat and natural gas sectors. The methodology is evaluated using a case study.