Most research on the agricultural impacts of climate change has focused on the major annual crops, yet perennial cropping systems are less adaptable and thus potentially more susceptible to damage. In regions where perennial crops are economically and culturally important, improved assessments of yield responses to future climate are needed to prioritize adaptation strategies. These impact assessments, in turn, must rely on climate and crop models that contain often poorly defined uncertainties. We evaluated the impact of climate change on six major perennial crops in California: wine grapes, almonds, table grapes, oranges, walnuts, and avocados. Outputs from multiple climate models were used to evaluate climate uncertainty, while multiple statistical crop models, derived by resampling historical databases, were used to address crop response uncertainties. We find that, despite these uncertainties, climate change in California is very likely to put downward pressure on yields of almonds, walnuts, avocados, and table grapes by 2050. Without CO2 fertilization or adaptation measures, projected losses range from 0 to >40% depending on the crop and the trajectory of climate change. Climate change uncertainty generally had a larger impact on projections than crop model uncertainty, although the latter was substantial for several crops. Opportunities for expansion into cooler regions were identified, but this adaptation would require substantial investments and may be limited by non-climatic constraints. Given the long time scales for growth and production of orchards and vineyards (30 years), climate change should be an important factor in selecting perennial varieties and deciding whether and where perennials should be planted.