Permeable bedrock aquifers in arid regions are being increasingly developed as water supplies, yet little is generally known about recharge processes and spatial and temporal variability. Environmental tracers from boreholes were used in this study to investigate net infiltration and recharge to the fractured Navajo Sandstone aquifer. Vadose zone tracer profiles at the Sand Hollow study site in southwestern Utah look similar to those of desert soils at other sites, indicating the predominance of matrix flow. However, recharge rates are generally higher in the Navajo Sandstone than in unconsolidated soils in similar climates because the sandstone matrix allows water movement but not root penetration. Water enters the vadose zone either as direct infiltration of precipitation through exposed sandstone and sandy soils or as focused infiltration of runoff. Net infiltration and recharge exhibit extreme spatial variability. High-recharge borehole sites generally have large amounts of vadose zone tritium, low chloride concentrations, and small vadose zone oxygen-18 evaporative shifts. Annual net-infiltration and recharge rates at different locations range from about 1 to 60 mm as determined using vadose zone tritium, 0 to 15 mm using vadose zone chloride, and 3 to 60 mm using groundwater chloride. Environmental tracers indicate a cyclical net-infiltration and recharge pattern, with higher rates earlier in the Holocene and lower rates during the late Holocene, and a return to higher rates during recent decades associated with anomalously high precipitation during the latter part of the 20th century. The slightly enriched stable isotopic composition of modern groundwater indicates this recent increase in precipitation may be caused by a stronger summer monsoon or winter southern Pacific El Niño storm track.