Fire is known to structure tree populations, but the role of broad-scale climate variability is less clear. For example, the influence of climatic "teleconnections" (the relationship between oceanic-atmospheric fluctuations and anomalous weather patterns across broad scales) on forest age structure is relatively unexplored. We sampled semiarid piñon-juniper (Pinus edulis-Juniperus osteosperma) woodlands in western Colorado, U.S.A., to test the hypothesis that woodland age structures are shaped by climate, including links to oceanic-atmospheric fluctuations, and by past fires and livestock grazing. Low-severity surface fire was lacking, as fire scars were absent, and did not influence woodland densities, but stand-replacing fires served as long-rotation (>400-600 years), stand-initiating events. Old-growth stands (>300 years old) were found in 75% of plots, consistent with a long fire rotation. Juniper and piñon age structures suggest contrasting responses during the past several centuries to dry and wet episodes linked to the Atlantic Multidecadal Oscillation (AMO) and Pacific Decadal Oscillation (PDO). Juniper density increased slightly during periods of drought, positive (warm) AMO (after approximately 10-year lag), and negative (cool) PDO. In contrast, piñon populations may still be recovering from a long, drought-filled period (AD 1620-1820), with pulses of recovery favored during cool AMO, warm PDO, and above-average moisture periods. Analysis of 20th-century tree establishment and instrumental climate data corroborate the long-term relationships between age structure and climate. After Euro-American settlement (AD 1881), livestock grazing reduced understory grasses and forbs, reducing competition with tree seedlings and facilitating climate-induced increases in piñons. Thus tree populations in these woodlands are in flux, affected by drought and wet periods linked to oceanic-atmospheric variability, Euro-American livestock grazing, and long-rotation, high-severity fires. Reductions in livestock grazing levels may aid ecological restoration efforts. However, given long-term fluctuations in tree density and composition, and expected further drought, thinning or burning to reduce tree populations may be misdirected.