During the highly anomalous conditions in early 2005, characterized by increased water temperatures and decreased productivity, male California sea lions adopted previously undocumented foraging behaviors. We investigated the movement and spatially explicit foraging behavior of males using satellite-linked data loggers and compared foraging behavior and effort between 2003--2004 and 2004--2005. Males foraged almost exclusively over the continental shelf during short trips in 2003--2004, while during anomalous conditions in 2004--2005 they altered their foraging effort by spending more time at sea and venturing up to 450 km offshore. Foraging trips in 2004--2005 were more than twice the distance and three times the duration of trips during 2003--2004. Our data indicated that the effects of climatic shifts during 2005 extended beyond the physical oceanography and lower trophic levels, to an apex predator; providing insight into the plasticity of foraging behavior and movement patterns of sea lions as they respond to environmental perturbations.