Conventional leak detection techniques require improvements to detect small leakage (<10%) in gas mixture pipelines under transient conditions. The current study is aimed to detect leakage in gas mixture pipelines under pseudo-random boundary conditions with a zero percent false alarm rate (FAR). Pressure and mass flow rate signals at the pipeline inlet were used to estimate mass flow rate at the outlet under leak free conditions using Hammerstein model. These signals were further used to define adaptive thresholds to separate leakage from normal conditions. Unlike past studies, this work successfully detected leakage under transient conditions in an 80-km pipeline. The leakage detection performance of the proposed methodology was evaluated for several leak locations, varying leak sizes and, various signal to noise ratios (SNR). Leakage of 0.15 kg/s—3% of the nominal flow—was successfully detected under transient boundary conditions with a F-score of 99.7%. Hence, it can be concluded that the proposed methodology possesses a high potential to avoid false alarms and detect small leaks under transient conditions. In the future, the current methodology may be extended to locate and estimate the leakage point and size.