Natural gas, which is an important energy source, is generally transported through natural gas pipelines that also pass through underwater. Underwater natural gas pipelines can be punctured for various reasons, especially for corrosion and shipping, fishing activities. Thus, detection and localization of the leakages has a crucial role in ensuring energy reliability and preserving the natural life. In this study, a novel signal strength based curve fitting method was proposed for positioning the leakages in the underwater natural gas pipelines. The performance of this method was analyzed by simulation studies using the parameters of a real life underwater natural gas pipeline and a time-varying (because of moving sea surface, underwater currents etc.) multipath doubly selective underwater acoustic channel. Numerical results show that for this time-varying multipath underwater acoustic channel, which is quite realistic, leakages can be positioned with low errors from kilometers away depending on the ambient noise and the sea wave height.