Dynamic simulation models can be used along with flow and pressure measurements, for on-line leak detection and identification in gas pipeline networks. In this two part paper, a methodology is proposed for detecting and localizing leaks occurring in gas pipelines. The main features of the proposed methodology are: (i) it is applicable to both single pipelines and pipeline networks and (ii) it considers non-ideal gas mixtures. In order to achieve the desired computational efficiency for on-line deployment, an efficient state estimation technique based on a transfer function model, previously developed by the authors, is embedded in a hypothesis testing framework. In Part-I of this paper, a detailed description of the methodology is presented, and its performance is evaluated using simulations on two illustrative pipeline systems. The proposed method is shown to perform satisfactorily even with noisy measurements and during transient conditions, provided there is sufficient redundancy in the measurements. © 2010 Elsevier Ltd.