In this paper, geographic information system, remote sensing and geostatistics were used to regionalize the potential natural aquifer recharge, especially in areas where data are scarce. Based on this, potential groundwater recharge zones were delineated using a combined analytical hierarchy process-multicriteria overlay analysis, to recognize favorable areas for natural recharge and to suggest suitable managed aquifer recharge (MAR) facilities to increase groundwater resources, within a regional complex hydrogeological system, belonging to the Jeffara of Medenine basin. The results show that the potential recharge sectors, covering 31% of the total area, are located mainly within Koutine, Ksar Chrarif, Sahel El Ababsa, and Mareth zones, which are characterized by a high infiltration capacity index favoring water percolation. These sectors are suitable for the implementation of MAR facilities that would offer a sustainable groundwater supply and increase recharge to the groundwater system. The obtained results were validated using receiver operating characteristic curve and correlations with 56 piezometric data. Such findings revealed that the proposed methodology assured good prediction and could, thus, be performed accurately in such arid regions to ensure optimum management of groundwater resources.