This paper proposes a novel optimal planning model for combined heat and power (CHP) in multiple energy systems of natural gas and electricity to benefit both networks by deferring investment for network owners and reducing use-of-system (UoS) charge for network users. The new planning model considers the technical constraints of both electricity and natural gas systems. A two-stage planning approach is proposed to determine the optimal site and size of CHPs. In the first stage, a long-run incremental cost matrix is designed to reflect CHP locational impact on both natural gas and electricity network investment, used as a criterion to choose the optimal location. In the second stage, CHP size is determined by solving an integrated optimal model with the objective to minimize total incremental network investment costs. The proposed method is resolved by the interior-point method and implemented on a practically integrated electricity and natural gas systems. Two case studies are conducted to test the performance for single and multiple CHPs cases. This paper enables cost-efficient CHP planning to benefit integrated natural gas and electricity networks and network users in terms of reduced network investment cost and consequently reduced UoS charges.