Archaeological data indicates that socially and politically complex hunter-gatherer societies had become well established on the southern California coast by A.D. 1300. Major developmental changes in sociopolitical complexity are generally considered to have taken place rapidly between AD 1150 and 1300. Recently, two hypotheses have been proposed to account for this rapid cultural evolution, both invoking stressful climatic conditions as an important trigger for cultural change. One suggests that the sociopolitical development was stimulated, in part, by multiple marine and terrestrial subsistence stresses, particularly low marine productivity resulting from regional warming. The other suggests that these developments were largely driven by decreases in terrestrial productivity and water availability linked to drought. Resolution of this debate has been hampered by insufficient paleoclimatic and archaeological data. We present a well-dated, relatively high resolution (25-year intervals) oxygen isotopic marine climate record and new archaeological data from the Northern Channel Islands for the last 3,000 years. These data strongly suggest that changes in human behavior associated with increasing cultural complexity: 1) accelerated after A.D. 500 and became dominant by A.D. 1300, 2) occurred during one of the coldest and most unstable marine climatic intervals of the Holocene (A.D. 450-1300), and 3) coincided with cool, dry terrestrial conditions. Incipient cultural complexity emerged during an interval marked by inferred high marine productivity, reduced terrestrial food and water availability, and large, unpredictable variations in terrestrial resource availability. Our records suggest a strong relationship during this time between climatically induced changes in environmental conditions and social, political, and economic responses, including the emergence of more intensified fishing, and increased sedentism, violence, and trade.