Study region: This study focuses on Arizona, a dryland state in the southwestern United States with marked variability in climate, elevation, and hydrogeology. Arizona spans two major physiographic regions, the Colorado Plateau and the Basin and Range, each exhibiting distinct hydrologic behavior. Study focus: We quantify long-term base-flow index (BFI) patterns and trends across Arizona and develop a predictive framework for ungauged basins. BFI was calculated at 205 USGS stream gauges using a recursive digital filter applied to multi-decadal streamflow records. Coincident trends in precipitation, temperature, and evapotranspiration were analyzed to assess climate-base-flow relationships. We trained an eXtreme Gradient Boosting (XGBoost) model on hydroclimatic and physiographic variables to estimate long-term BFI from 1991 to 2020 at the 8digit Hydrologic Unit Code (HUC) scale. New hydrological insights for the region: Groundwater discharge accounts for approximately 32 % of streamflow in Arizona, with substantial spatial variability linked to topography, land cover, and climate. High BFI values are found in forested headwaters with spring-fed and snowmelt-driven systems, while low values dominate the state's arid lowlands. Declining BFI trends were most pronounced in monsoon-dominated, warm-dry, and low-slope basins. Precipitation was the strongest climate correlate of BFI trends, underscoring the importance of climate variability for dryland base flow. This integration of observational records and machine learning provides new insights into groundwater-surface water interactions and offers a transferable framework for water resource assessment in data-scarce dryland regions globally.