This study proposes a decentralised methodology to deal with the optimal energy flow (OEF) problem of the electricity–natural gas system (EGS). The OEF problem of EGS is formulated as a multi-stage dynamic programming (DP) process, and the approximate DP algorithm is used to decompose it into subproblems. The independent decision of each subproblem can be made by solving Bellman's equation, requiring just a moderate interchange of information among different subproblems. Such that the information privacy and dispatch independency of subsystems (including electricity and natural gas (NG) subsystems) can be ensured. Different from most existing decentralised algorithms, the impact of one subproblem's decision on other subproblems can be estimated in the proposed algorithm, and the parameters of the proposed algorithm are not required for tuning, which makes more sense in real applications. Furthermore, an improved linear cut technique is proposed to handle the non-convexity of the NG network model, so that the tightness of all gas flow constraints can be ensured. Case studies containing small, large and complicated EGSs validate the effectiveness of the proposed approach.